代码随想录算法训练营第三十四天 | 62.不同路径 63.不同路径II 343.整数拆分

62.不同路径

题目链接：62. 不同路径 - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：动态规划中如何初始化很重要！| LeetCode：62.不同路径_哔哩哔哩_bilibili

思路：机器人位于一个 m x n 网格，每次只能向下或者向右移动一步，达到网格的右下角总共有多少条不同的路径

机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。

1.确定dp数组以及下标的含义

dp[i][j] ：表示从(0,0)出发，到(i, j)有dp[i][j]条不同的路径。

2.确定递推公式

想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]，

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

3.dp数组的初始化

首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。

4.确定遍历顺序

dp[i][j]都是从其上方和左方推导而来，从左到右一层一层遍历就可以了。

5.举例推导dp数组

时间复杂度：O(m × n)    空间复杂度：O(m × n)

63. 不同路径 II

题目链接：63. 不同路径 II - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II_哔哩哔哩_bilibili

思路：机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点，中间有障碍物

1.确定dp数组以及下标的含义

dp[i][j] ：表示从(0 ,0)出发，到(i, j)有dp[i][j]条不同的路径。

2.确定递推公式

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

有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。

3.dp数组初始化

因为从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。

如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0,下标(0, j)的初始化情况同理。

代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理

4.确定遍历顺序

从左到右一层一层遍历

5.举例推导dp数组

时间复杂度：O(n × m)  空间复杂度：O(n × m)

343. 整数拆分

题目链接：343. 整数拆分 - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分_哔哩哔哩_bilibili

思路：给定一个正整数 n，将其拆分为至少两个正整数的和，返回可以获得的最大乘积

1.确定dp数组以及下标的含义

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

2.确定递推公式

dp[i]最大乘积来自于，一个是j * (i - j) 直接相乘，一个是j * dp[i - j]，

j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。

递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

也就是Max｛不拆i-j,  拆i-j （且拆后乘积最大）,  到上一轮(i-1)为止的最大乘积}，放入dp[i]是因为dp[i]最后的值应该时当i固定j循环时，每一整轮的最大值，而不是每次j变化的最大值

3.dp的初始化

dp[2] = 1

4.确定遍历顺序

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

5.举例推导dp数组

时间复杂度：O(n^2)    空间复杂度：O(n)