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

#include <vector>
class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> dp(n + 1, 25000000);
        for (int i = 1; i <= m; ++i) {
            if (i == 1) {
                dp[0] = 0;
            } else {
                dp[0] = 25000000;
            }
            for (int j = 1; j <= n; ++j) {
                dp[j] = min(dp[j], dp[j - 1]) + matrix[i - 1][j - 1];
            }
        }
        return dp[n];
    }
};

思路：常规动态规划。dp[i][j]表示走到(i, j)的最小路径和，只可能从(i - 1, j)或(i, j - 1)走来。