代码随想录算法训练营第三十九天| LeetCode62.不同路径、LeetCode63.不同路径II、LeetCode343. 整数拆分
#LeetCode 62. Unique Path
#LeetCode 62. 视频讲解：动态规划中如何初始化很重要！| LeetCode：62.不同路径_哔哩哔哩_bilibili
动态规划五部曲：
1. 确定dp[i][j] 的含义，在这里dp[i][j] 代表第i, j 位置的路径数目
2. 递推公式，题目规定，移动的方向只能是右方或者下方，所以当前位置i, j 的路径数目只能通过i-1, j 或者i, j-1 再移动一步得到。所以是dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. dp数组应该如何初始化，根据递推公式得到，第一行与第一列都需要初始化来保证递推公式的有效性。他们的值都是1 ，因为能够到达的路径数目是1
4. 遍历顺序，是从前向后，因为当前位置的路径，是通过前一个格子得到的
5. 打印dp 数组，可以帮助检查
代码：
class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int j = 0; j < n; j++) {dp[0][j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}#LeetCode 63. Unique Paths II
#LeetCode 63. 视频讲解：动态规划，这次遇到障碍了| LeetCode：63. 不同路径 II_哔哩哔哩_bilibili
与上一个题目不同的地方是，添加了障碍，如果遇到了障碍，那么这个点的路线数目为0，之后的计算时，自动不会再考虑经过障碍的路线了。
需要在多个地方添加限定，因为根据题目要求来看，是不能向上走的。
代码：
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {return 0;}for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {dp[i][0] = 1;}for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {dp[0][j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = (obstacleGrid[i][j] == 0 ? dp[i-1][j] + dp[i][j-1] : 0);}}return dp[m-1][n-1];}
}#LeetCode 343. Integer Break
#LeetCode 343. 视频讲解：动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分_哔哩哔哩_bilibili
如果和是确定的，那么拆分的几个数字越相近，积越大。
动态规划五部曲：
1. 确定dp[i] 的含义，在这里dp[i] 代表对i 进行拆分得到最大的乘积dp [i]
2. 递推公式，题目规定，dp[i] = j * (i - j), dp[i] = j * dp[i - j]
3. dp数组应该如何初始化，dp[0] 和dp[1] 是没有意义的，初始化为0
4. 遍历顺序，是从前向后
5. 打印dp 数组，可以帮助检查
代码：
class Solution {public int integerBreak(int n) {int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 0;dp[2] = 1;for (int i = 3; i <= n; i++) {for (int j = 1; j < i; j++) {dp[i] = Math.max(Math.max(j * (i - j), j * dp[i - j]), dp[i]);}}return dp[n];}
}