题解 | 矩阵的最小路径和

#include <functional>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size();
        int m = matrix[0].size();
        //cout << "n=" << n << " m=" << m << endl;
        vector<vector<int>> dp(n, vector<int>(m, 0));

        dp[0][0] = matrix[0][0];
        for (int j = 0; j < m; j++) {
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
            //cout << "dp[0][j]=" << dp[0][j] << endl;
        }
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
            //cout << "dp[i][0]=" << dp[i][0] << endl;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
                //cout << "dp[" << i << "][" << j << "]=" << dp[i][j] << endl;
            }
        }
        
        return dp[n - 1][m - 1];
        /*int minSum = 0;

        minSum += matrix[0][0];
        for (int i=0, j=0; i<m && j<n; )
        {
            if(matrix[i][j+1] <= matrix[i+1][j])
            {
                minSum += matrix[i][j+1];
                cout << "matrix["<<i<<"]["<<j << "+1]"<< matrix[i][j+1] <<endl;
                j++;
            }
            else {
                minSum += matrix[i+1][j];
                cout << "matrix[i+1][j]"<< matrix[i+1][j] <<endl;
                i++;
            }
        }
        minSum += matrix[m-1][n-1];
        cout << "matrix[m-1][n-1]"<< matrix[m-1][n-1] <<endl;
        return minSum;*/
    }
};