[动态规划]---part2

前言

作者：小蜗牛向前冲

专栏：小蜗牛算法之路

专栏介绍：\"蜗牛之道，攀登大厂高峰，让我们携手学习算法。在这个专栏中，将涵盖动态规划、贪心算法、回溯等高阶技巧，不定期为你奉上基础数据结构的精彩算法之旅。一同努力，追逐技术的星辰大海。\"

目录

一、不同路径II（medium）

a、解题思路

b、代码

二、礼物的最⼤价值（medium）

a、解题思路

b、代码

三、下降路径最⼩和（medium）

a、解题思路

b、代码

四、 最⼩路径和（medium）

a、解题思路

b、代码

五、地下城游戏（hard）

a、解题思路

b、代码

本期：继续手撕动态规划：不同路径II（medium），礼物的最⼤价值（medium），下降路径最⼩和（medium），最⼩路径和（medium），地下城游戏（hard）

继续刷动态规划相关算法题，如果不清楚什么是动态规划的可以看这里：[动态规划]---part1

一、不同路径II（medium）

一个机器人位于一个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(vector<vector>& obstacleGrid) { }};

a、解题思路

这道题和同路径I的解题思路非常相似，但是就是在机器人找到终点的过程中，会有障碍物。

1、转态表示

首先我们想以i，j位置为结尾表示什么

dp[i][j表示：以i,j位置结尾的时候，机器人到这里有多少条路径

2、状态转移方程

根据最近的一个位置划分：

当前位置有障碍物：

返回0

当前位置没有障碍物：

dp[i][j] = dp[i-1][j]+dp[i][j-1];

大家可能会想，我要是在[i-1][j]或者[i][j-1]遇到障碍物了，状态转态方程还可以相加吗?

其实是可能的，因为我在遇到障碍物是返回0的，而0对相加的结果是没有影响的。

3、初始化

这里我们要初始化，就是在二维数组多开一行和一列，但我们要思路多开的行列填什么呢（一切都是为了填表走服务）？，很明显，机器人是在[1,1]位置开始走的，也就说[1,1]位置肯定要为1（当最特色情况起点就是中点），所以我们只要保证，dp[1][0]==1或者dp[0][1]==1即可。其他位置看情况决定。

这里除了要注意填表的初始化，还要注意下标映射关心的改变：

obstacleGrid[0][0]-------->映射dp[1][1];

obstacleGrid[2][3]-------->映射dp[3][4];

也就是横着纵坐标都要加1

4、 填表顺序

从上往下填写每一行，每一行都是从左往又开始填写

5、返回值

dp[m][n]

b、代码

class Solution {public: int uniquePathsWithObstacles(vector<vector>& obstacleGrid) { int m = obstacleGrid.size();//有多少行 int n = obstacleGrid[0].size();//有多少列 //创建dp表 vector<vector> dp(m + 1, vector(n