当前位置：首页 > news >正文

代码随想录第34天|动态规划

news 来源：原创 2024/9/19 14:45:09

62.不同路径

代码随想录

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

代码随想录

dp[i,j] 数组含义：从起始位置【0，0】到【i，j】有多少种不同的路径
递推公式：只能从左侧dp[i][j-1]走一步，或者从上面dp[i-1][j]走一步
1. dp[i][j] = dp[i-1][j]+dp[i][j-1]
初始化：最上侧和最左侧初始化
1. dp[0][j]~dp[0][n-1] = 1;
2. dp[i][0]~dp[m-1][0] = 1;
遍历顺序：只能从左往右遍历，从上往下遍历
打印

代码

class Solution {public int uniquePaths(int m, int n) {int[][] paths = new int[m][n];//初始化for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(i==0){paths[0][j]=1;}else if(j==0){paths[i][0]=1;}else{paths[i][j] = paths[i-1][j]+paths[i][j-1];}}}return paths[m-1][n-1];}
}

63.不同路径II

https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.htmlhttps://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html

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

代码随想录

只需要在上一题的基础上将有障碍物的位置标记为0就行。

任何时刻都要坚守dp五部曲：

dp[i,j] 数组含义：从起始位置【0，0】到【i，j】有多少种不同的路径
递推公式：只能从左侧dp[i][j-1]走一步，或者从上面dp[i-1][j]走一步
1. if(dp[i,j]==0) dp[i][j] = dp[i-1][j]+dp[i][j-1];
2. else dp[i][j] = 0;//这里不需要赋零，初始化就已经完成了。
初始化：最上侧和最左侧初始化
1. dp[0][j]~dp[0][n-1] = 1;if(dp[0][j]==1)break;
2. dp[i][0]~dp[m-1][0] = 1;if(dp[i][0]==1)break;
遍历顺序：只能从左往右遍历，从上往下遍历
打印

需要主义，首先判断重点有无障碍物，如果有直接返回。

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];if(obstacleGrid[m-1][n-1]==1)return 0;//横向初始化for (int i = 0; i < n&&(obstacleGrid[0][i]==0); i++) {dp[0][i]=1;}//纵向初始化for (int j = 0; j < m && (obstacleGrid[j][0] == 0); j++) {dp[j][0]=1;}//递推过程for(int i = 1;i<m;i++){for (int j = 1; j < n; j++) {if(obstacleGrid[i][j]==0){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m-1][n-1];}
}