带权值的最小路径和

设dp[i][j]表示行数为i，列数为j的矩阵中，从左上角到右下角的最小路径和。状态公式：

1. 当i>=2 && j>=2时，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]
2. 基准1: dp[1][k] = dp[1][k-1] + grid[0][k-1]
3. 基准2: dp[k][1] = dp[k-1][1] + grid[k-1][1]

状态公式的解释如下：

1. 如果行数和列数都大于2，那么当前点的最小路径和为正上方节点最小路径和与正左方节点最小路径和中的较小者，加上当前节点的值
2. 只有一行时，累加即可
3. 只有一列时，同样累加即可

代码如下：

//
// Created by jt on 2020/8/30.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& grid) {
        // write code here
        if (grid.size() < 1) return 0;
        vector<vector<int> > dp(grid.size()+1, vector<int>(grid[0].size()+1, 0));
        for (int i = 1; i <= grid.size(); ++i) { dp[i][1] = dp[i-1][1] + grid[i-1][0]; }
        for (int i = 1; i <= grid[0].size(); ++i) { dp[1][i] = dp[1][i-1] + grid[0][i-1]; }
        for (int i = 2; i <= grid.size(); ++i) {
            for (int j = 2; j <= grid[0].size(); ++j) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])
                           + grid[i-1][j-1]; // 别忘了加上当前值
            }
        }
        return dp[grid.size()][grid[0].size()];
    }
};