动态规划太难了？是你没有找对方法，四题带你搞懂动态规划！

💯 博客内容：动态规划刷题

😀 作  者：陈大大陈

🚀 个人简介：一个正在努力学技术的准前端，专注基础和实战分享 ，欢迎私信！

💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘

目录

 一.91. 解码方法 - 力扣（LeetCode）

 二.LCR 098. 不同路径 - 力扣（LeetCode）

三.63. 不同路径 II - 力扣（LeetCode）

四.LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

---

 

 动态规划的题目说到底其实就五步。

1.状态表示

2.列出状态转移方程

3.初始化

4.确定填充顺序

5.确定返回值

接下里的题目就将按照这五步来带大家分析。

 一.91. 解码方法 - 力扣（LeetCode）

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

 题解代码

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n+1);
        dp[0]=(s[0]!='0');
        if(s[0]!='0'&&s[1]!='0')
        dp[1]=1;
        int t=(s[0]-'0')*10+s[1]-'0';//前两个位置所表示的数字
        if(t>=10&&t<=26) dp[1]+=1;
        for(int i=2;i<=n;i++)
        {
            if(s[i]!='0') dp[i]+=dp[i-1];//单独编码的情况
            int t=(s[i-1]-'0')*10+s[i]-'0';//共同编码的情况
            if(t>=10&&t<=26)
            dp[i]+=dp[i-2];
        }
      return dp[n-1];
    }
};

首先是状态表示，dp[n]就代表到n这个位置编码的总数。

然后列出状态转移方程，根据最近的一步来分析问题。

 分析如图，列出状态转移方程为dp[i]=dp[i-1](条件成立时)+dp[i-2](条件成立时)。

第三步初始化，这道题需要初始化前两个位置，注意判断第二个位置是否可以和第一个位置组合。

第四步确定填充顺序，这道题目是经典的自上而下，从左到右。

第五步确定返回值，字符串最后一个字母是在n-1的位置。所以返回dp[n-1]。

 二.LCR 098. 不同路径 - 力扣（LeetCode）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

 

首先是状态表示，dp[n]就代表到n这个位置路径的总数。

然后列出状态转移方程，根据最近的一步来分析问题。

到达dp[i][j]这个位置，只能通过dp[i-1][j]和dp[i][j-1]。

所以状态转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-1]。

初始化的时候要注意，第一行和第一列会越界，所以咱们定义stl要多一行多一列。

 

如图，绿色部分是咱们多添加的部分。

对绿色部分的虚拟节点进行初始化，要保证后面表的结果正确。

还有就是要注意下标，因为咱们的下标是从1开始的。 

第四步确定填充顺序，这道题目是经典的自上而下，从左到右。

最后是返回值，最后一个位置即为咱们要返回的值。

三.63. 不同路径 II - 力扣（LeetCode）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

 

class Solution {
public:
    int uniquePathsWithObstacles(vectorint>>& ob) {
        int m=ob.size(),n=ob[0].size();
        vectorint>> 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]==0)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

这道题目的答题思路和上题基本相同，需要处理的只有障碍物的问题。

有障碍物的地方无法到达，那么加上限制条件即可。

需要注意的是，咱们下标从1开始，对应题目所给的二维数组时要减一。

四.LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1:

输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝

提示：

• 0 < frame.length <= 200
• 0 < frame[0].length <= 200

class Solution {
public:
    int jewelleryValue(vectorint>>& frame) {
        int m=frame.size(),n=frame[0].size();
        vectorint>> dp(m+1,vector<int>(n+1));
        
        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])+frame[i-1][j-1];  
            }
        }
        return dp[m][n];
    }
};

 

 首先是状态表示，dp[i][j]表示到达[i,j]位置时，珠宝的最大价值。

然后是列出状态转移方程，珠宝选购的移动方式和上面两题很像。

咱们可以套用，唯一的不同是，要加上此位置珠宝的价值，因为要计算最大价格。

dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i][j]。

初始化的时候，为了防止越界，咱们同样是多开一行一列。

因为珠宝的价值不会小于0，所以虚拟节点的值就初始化为0即可。

填表顺序，自上而下，从左到右。

返回值即为最后一个位置的值。

结语

动态规划这一块大家还是要跟着教程学，自己做题再看答案的话很容易被答案绕晕，因为答案的思路都是不固定的，大家很容易搞混。