[动态规划]---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 映射dp[3][4];

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

  4、 填表顺序

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

  5、返回值

  dp[m][n]

  b、代码

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