题解 | #矩阵的最小路径和#

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        int m[matrix.size()][matrix[0].size()];
        int i;
        int j;
        m[0][0] = matrix[0][0];
        for(i = 1, j = 0; i < matrix.size();i++)
        {
            m[i][j] = matrix[i][j] + m[i-1][j];
        }
        for(i = 0, j = 1; j < matrix[0].size(); j++)
        {
            m[i][j] = matrix[i][j] + m[i][j-1];
        }
        for(i = 1, j = 1; i < matrix.size() && j < matrix[0].size(); i++, j++)
        {
            for(int k = i; k < matrix.size(); k++)
            {
                m[k][j] = min(m[k-1][j]+matrix[k][j], m[k][j-1]+matrix[k][j]);
            }
            for(int q = i; q < matrix[0].size(); q++)
            {
                m[i][q] = min(m[i-1][q]+matrix[i][q], m[i][q-1]+matrix[i][q]);
            }
        }
        if(i < matrix.size())
        {
            for(j = matrix[0].size()-1; i < matrix.size();i++)
            {
                m[i][j] = min(m[i-1][j], m[i][j-1]) + matrix[i][j];
            }
        }
        if(j < matrix[0].size())
        {
            for(i = matrix.size()-1; j < matrix[0].size();j ++)
            {
                m[i][j] = min(m[i-1][j], m[i][j-1]) + matrix[i][j];
            }
        }
//         for(i = 0; i < matrix.size();i++)
//         {
//             for(j = 0; j < matrix[0].size(); j++)
//             {
//                 cout<< m[i][j] << " ";
//             }
//             cout<<endl;
//         }
        return m[matrix.size()-1][matrix[0].size()-1];
    }

};