算法沉淀——动态规划之路径问题（leetcode真题剖析）

算法沉淀——动态规划之路径问题

• 01.不同路径
• 02.不同路径 II
• 03.珠宝的最高价值
• 04.下降路径最小和
• 05.最小路径和
• 06.地下城���戏

  01.不同路径

  题目链接：https://leetcode.cn/problems/unique-paths/

  一个机器人位于一个 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 public: int uniquePaths(int m, int n) { vector for(int j=1;j if(i==1&&j==1) continue; dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m][n]; }};h202.不同路径 II/h2 p题目链接：https://leetcode.cn/problems/unique-paths-ii//p p一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。/p p机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。/p p现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？/p p网格中的障碍物和空位置分别用 1 和 0 来表示。/p p示例 1：/p pre 输入：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 public: int uniquePathsWithObstacles(vector int m=obstacleGrid.size(),n=obstacleGrid[0].size(); vectorpublic: int jewelleryValue(vector int m=frame.size(),n=frame[0].size(); vectorpublic: int minFallingPathSum(vector int m=matrix.size(),n=matrix[0].size(); vectorpublic: int minPathSum(vector int m=grid.size(),n=grid[0].size(); vectorpublic: int calculateMinimumHP(vector int m=dungeon.size(),n=dungeon[0].size(); vector dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]; dp[i][j]=max(1,dp[i][j]); } return dp[0][0]; }};