LeeCode Practice Journal | Day_DP02

2024/10/24 9:28:24 来源：https://blog.csdn.net/Janniam/article/details/140935486 浏览: 次关键词：LeeCode Practice Journal | Day_DP02

1、确定dp数组及下标含义
2、确定递推公式
3、dp数组初始化
4、确定遍历顺序
5、举例推导dp数组

62. 不同路径

题目：62. 不同路径 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
二维斐波那契数列

solution

public class Solution {public int UniquePaths(int m, int n) {int[][] dp = new int[n][];for(int x = 0; x < n; x ++){dp[x] = new int[m]; }for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){if(i == 0 || j == 0) dp[i][j] = 1;else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];               }}return dp[n - 1][m - 1];}
}

summary

dp：

1、dp[m][n]：到（m,n）位置有dp[m][n]种不同路径
2、dp[m][n] = dp[m - 1][n] + dp[m][n - 1]
3、dp[0][n] = 1; dp[m][0] = 1
4、从左上向右下

错误：

返回答案为dp[n - 1][m - 1]，而不是dp[n][m]

63. 不同路径Ⅱ

题目：63. 不同路径 II - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)

加入条件判断

solution

public class Solution {public int UniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.Length;int n = obstacleGrid[0].Length;int[][] dp = new int[m][];for (int i = 0; i < m; i ++){dp[i] = new int[n];}for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){if(obstacleGrid[i][j] == 1) dp[i][j] = 0;else{if(i == 0 && j == 0) dp[i][j] = 1;else if(i == 0) dp[i][j] = dp[0][j - 1];else if(j == 0) dp[i][j] = dp[i - 1][0];else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}
}

summary

1、dp[m][n]：到（m,n）位置有dp[m][n]种不同路径
2、dp[m][n] = dp[m - 1][n]（无障碍） + dp[m][n - 1]（无障碍）
3、dp[0][n] = 1; dp[m][0] = 1
4、从左上向右下

错误:

1、int[ , ] VS int[][]：

int[,] 是一个真正的二维数组（矩阵），可以使用 GetLength 方法。
int[][] 是一个数组的数组，其长度是通过 Length 属性来获取的。

343. 整数拆分

题目：343. 整数拆分 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
笨比上线。。。

solution

public class Solution {public int IntegerBreak(int n) {if (n == 2) return 1;if (n == 3) return 2;int[] dp = new int[n + 1];// Initialize base casesdp[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 1; j < i; j++) {dp[i] = Math.Max(dp[i], Math.Max(j * (i - j), j * dp[i - j]));}}return dp[n];}
}

summary

1、dp[n]：n的拆分最大乘积
2、dp[n] = Max(dp[i], Math.Max(j * (i - j), j * dp[i - j])) 1 < m < n/2
3、dp[1] = 1

推导：

96. 不同的二叉搜索树

题目：96. 不同的二叉搜索树 - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
忽然发现动态规划的本质好像是找规律。。。

solution

public class Solution {public int NumTrees(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i ++){for(int j = 1; j <= i; j ++){dp[i] += dp[i - j] * dp[j - 1];}}return dp[n];}
}