第九章 动态规划part02
今天开始逐渐有 dp的感觉了，前 两题 不同路径，可以好好研究一下，适合进阶
详细布置
62.不同路径
本题大家掌握动态规划的方法就可以。 数论方法 有点非主流，很难想到。
https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
视频讲解：https://www.bilibili.com/video/BV1ve4y1x7Eu
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 = 1; 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];
}
}
63. 不同路径 II
视频讲解：https://www.bilibili.com/video/BV1Ld4y1k7c6
错误思路：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int x = 0, y = 0;
for(int i = 0; i < m; i ++){
for(int j = 0; j < n; j ++){
if(obstacleGrid[i][j] == 0){
x = i;
y = j;
}
}
}
return uniquePaths(m, n) - uniquePaths(m-x, n-y);
}
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 = 1; 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];
}
}
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if(obstacleGrid[0][0] == 1) return 0;// 必须要特殊判断
int[][] dp = new int[m][n];
for(int i = 0; i < m && obstacleGrid[i][0] != 1; i ++) dp[i][0] = 1;
for(int j = 1; j < n && obstacleGrid[0][j] != 1; j ++) dp[0][j] = 1;
for(int i = 1; i < m; i ++){
for(int j = 1; j < n; j ++){
if(obstacleGrid[i][j] != 1) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//相当于给障碍物 赋0
}
}
return dp[m-1][n-1];
}
}
343. 整数拆分 （可跳过）
本题思路并不容易想，一刷建议可以跳过。如果学有余力，可以看视频理解一波。
https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
视频讲解：https://www.bilibili.com/video/BV1Mg411q7YJ
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
for(int i = 3; i <= n; i ++){
int max = 0;
for(int j = 1; j < i; j ++){
int temp = Math.max(j * (i - j) , j * dp[i - j]);
if(temp > max) max = temp;
}
dp[i] = max;
}
return dp[n];
}
}
另一个最大值比较：
dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
96. .不同的二叉搜索树 （可跳过）
本题思路并不容易想，一刷建议可以跳过。 如果学有余力，可以看视频理解一波。
视频讲解：https://www.bilibili.com/video/BV1eK411o7QA
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[j -1]*dp[i - j];
}
}
return dp[n];
}
}
