动态规划路径问题入门：核心定义与 LeetCode 例题解析

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        dp[0][1]=1;
        for(int i=1;i<=m;++i) {
            for(int j=1;j<=n;++j) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

3.2 LeetCode 63. 不同路径 II

这道题目的话和上面那一道题目很像，都是在一个二维数组里面，计算机器人从左上角走到右下角的路径总数。唯一的区别就是这道题给的数组里面是存在石头的，也就是需要机器人绕路的点。

所以在这道题里面它的状态表示就是走到当前位置的路线数。

所以在这道题里面它的状态转移方程就是 dp[i][j]=dp[i-1][j]+dp[i][j-1]，如果遇到石头的话就是 0。

我们在这边需要多设置一行一列，它的初始化就是在把虚拟位置的 [0][1] 给设置为 1.

填表顺序就是一行一行的填写。

返回值就是 dp[m][n]。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        int m=ob.size();
        int n=ob[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        dp[0][1]=1;
        for(int i=1;i<=m;++i) {
            for(int j=1;j<=n;++j) {
                if(ob[i-1][j-1]==1) dp[i][j]=0;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

3.3 LeetCode LCR 166. 珠宝的最高价值

这道题的话和前面两道题目不太一样，题目是要求我们到达右下角时整个途中经过的数组数字和最大。

这道题的话是带着一点贪心的思想在里面的，我们在设计代码的时候也是同样的，就是要让 dp 表里面的每一个位置都是代表走到这个位置时所能达到的最大值。

所以在这道题里面它的状态表示就是走到当前位置时能达到的最大值。

所以在这道题里面它的状态转移方程就是 dp[i][j]=max(dp[i-1][j],dp[i][j-1])+f[i-1][j-1]。

(+f[i-1][j-1] 是因为还需要加上当前位置的值，也就是走到这个位置时的自身值)

我们在这边需要多设置一行一列，它的初始化就是在把虚拟位置的 [0][1] 给设置为 1.

填表顺序就是一行一行的填写。

返回值就是 dp[m][n]。

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& f) {
        int m=f.size();
        int n=f[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        dp[1][1]=f[0][0];
        for(int i=1;i<=m;++i) {
            for(int j=1;j<=n;++j) {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+f[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};