前言
在上一篇文章 动态规划从入门到LeetCode - 掘金 (juejin.cn) 中, 我们学习了怎么去做动态规划类的题目, 并进行了简单题目的练习
今日任务:
动态规划解题五部曲
- 确定 dp 数组以及下标的含义
- 确定递推公式
- dp 数组如何初始化
- 确认遍历顺序
- 举例推导 dp 数组
62. 不同路径
题目描述
一个机器人位于一个 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 数组以及下标的含义:
本题 机器人 处于 网格 中, 他有 两个 前进的方向, 那么本题就和上一篇文章做的 爬楼梯等题不一样了, dp 数组应该是 ==> dp[i][j] i代表 x轴 方向前进, j 代表 y轴 方向前进, dp[i][j] 代表到达该点的路径条数 - 确定递推公式
由于本题有两种方向可选, 且到达的点位是固定可知的, 所以 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp数组 如何初始化
- 因为只能向下或者向右前进
- 所以 dp[i][0] = 1;
- 同理 dp[0][j] = 1;
- 确认遍历顺序
- 因为只能向下或者向右前进
- 所以直接从左向右遍历就可以了
- 举例推导 dp数组
- 当 m = 3, n = 7时, 推导每个坐标值如下所示
网络异常，图片无法展示
|
代码展示
public int uniquePaths(int m, int n) { // 确定 dp 数组 int[][] dp = new int[m][n]; // 循环遍历数组 for (int i = 0; i < m; i++) { for (int j = 0;j < n; j++) { // 初始化 dp 数组 if (i == 0 || j == 0){ dp[i][j] = 1; continue; } // 递推公式 dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } // 返回 机器人 抵达右下角有多少种路径 return dp[m-1][n-1]; } 复制代码
提交结果
网络异常，图片无法展示
|
63. 不同路径 II
题目描述
一个机器人位于一个 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.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]为0或1
思路分析
首先获取网格 x,y 的长度, 然后创建新数组
- 确定dp数组以及下标的含义
本题和上一题的区别就是多出了 障碍物, 那么 dp数组 的下标及其含义是不变的, 依旧是到达该点位的路径条数 - 确定递推公式
一样的, dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp数组的初始化
- 只能向下或者向右前进, 但是本题引入了 障碍物的情况, 所以初始化也要有相应的改变
- 所以 dp[i][0] = obstacleGrid[i][0] == 0 ? 1 : 0;
- 同理 dp[0][j] = obstacleGrid[i][0] == 0 ? 1 : 0;
- 确定遍历顺序
- 和上一题一样的, 从左到右, 从上到下双层 for 循环进行遍历
- 举例推导这边就不举例了
代码展示
public int uniquePathsWithObstacles(int[][] obstacleGrid) { // 获取长度 int x = obstacleGrid.length; int y = obstacleGrid[x - 1].length; // 判断边界, 起点和终点不能有障碍物 if (obstacleGrid[0][0] == 1 || obstacleGrid[x - 1][y - 1] == 1){ return 0; } // 创建 dp 数组 int[][] dp = new int[x][y]; // 初始化 dp 数组 for (int i = 0; i < x && obstacleGrid[i][0] == 0; i++) { dp[i][0] = 1; } for (int i = 0; i < y && obstacleGrid[0][i] == 0; i++) { dp[0][i] = 1; } // 推导下标值 for (int i = 1; i < x; i++) { for (int j = 1; j < y; j++) { // 如果有障碍物, 则赋予这个坐标为 0 dp[i][j] = obstacleGrid[i][j] == 0 ? dp[i-1][j] + dp[i][j-1] : 0; } } return dp[x - 1][y - 1]; } 复制代码
提交结果
网络异常，图片无法展示
|
错误分析
第一次错误
public int uniquePathsWithObstacles(int[][] obstacleGrid) { int length1 = obstacleGrid.length; int length = obstacleGrid[length1 - 1].length; for (int i = 0; i < length1; i++) { for (int j = 0; j < obstacleGrid[i].length; j++) { if (i == 0){ // 如果是障碍物就给他 0 if (obstacleGrid[i][j] == 1){ obstacleGrid[i][j] = 0; break; } obstacleGrid[i][j] = 1; continue; }else if (j == 0){ obstacleGrid[i][j] = obstacleGrid[i][j] == 0 ? 1 : 0; continue; } obstacleGrid[i][j] = obstacleGrid[i][j] == 0 ? obstacleGrid[i-1][j] + obstacleGrid[i][j-1] : 0; } } return obstacleGrid[length1 - 1][length - 1]; } 复制代码
网络异常，图片无法展示
|
入口放障碍也是没想到的, 下面是评论...
网络异常，图片无法展示
|
鉴于上述结果, 我在代码中新增了边界控制判断, 如果起点或者终点有障碍, 则直接返回 0, 新增判断代码如下, 然后就出现了第二次错误
if (obstacleGrid[0][0] == 1 || obstacleGrid[length1 - 1][length - 1] == 1){ return 0; } 复制代码
第二次错误
这是真的bug, 待我改一改
不得不说, 这个代码写的跟**屎山**一样, 多搞几个 for循环, 改一手吧, 不偷懒, 而是**新建一个 dp 数组来存储到达某个坐标点的路径数目**, 具体可看 代码提交 部分 复制代码
网络异常，图片无法展示
|
343. 整数拆分
题目描述
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 复制代码
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 复制代码
提示:
2 <= n <= 58
思路分析
- 确定 dp数组 以及下标的含义
dp[i]: 第 i 个数的最大值 - 确定递推公式从 i 开始遍历, 遍历到 <= n, 然后 j 再从 1 开始遍历, 遍历到 j <= i-j, 也就是 j 最大值是 i-1, 有两种情况能够获取到 dp[i]
- dp[i] = j*(i-j); 计算两个数相乘
- dp[i] = j*dp[i-j]; 计算两个及以上的数相乘 (dp[i-j] 是第 i-j 个数的最大值)
- dp数组的初始化
默认 dp[2] = 1, dp[0] 和 dp[1]不用管, 因为2<=n - 确认遍历顺序
从左往右开始遍历, i 从 3 开始, j 从 1开始遍历
for (int i = 3; i <= n; i++) { for (int j = 1; j <= i-j; j++) { // 递推公式 dp[i] = Math.max(dp[i], Math.max((i-j)*j, dp[i-j]*j)); } } 复制代码
- 举例推导 pd数组
代码展示
public int integerBreak(int n) { // 创建 dp数组 int[] dp = new int[n + 1]; // 初始化 dp数组 dp[2] = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j <= i-j; j++) { // 递推公式 dp[i] = Math.max(dp[i], Math.max((i-j)*j, dp[i-j]*j)); } } return dp[n]; } 复制代码
提交结果
网络异常，图片无法展示
|
总结
经过这三道题的练习, 我对动态规划有了更深一步的理解, 真的就是循序渐进的学习, 奥利给
