做磁力网站,微博营销的定义,seo对各类网站的作用,wordpress绑定题目链接#xff1a;62.不同路径 代码随想录 视频讲解#xff1a;动态规划中如何初始化很重要#xff01;| LeetCode#xff1a;62.不同路径_哔哩哔哩_bilibili 因为只能向右或则向下走#xff0c;所以到第i#xff0c;j位置有dp[i][j]的方法数等于 dp[i - 1] 的方法数加…题目链接62.不同路径 代码随想录 视频讲解动态规划中如何初始化很重要| LeetCode62.不同路径_哔哩哔哩_bilibili 因为只能向右或则向下走所以到第ij位置有dp[i][j]的方法数等于 dp[i - 1] 的方法数加上 dp[i][j - 1]方法数
我们要知道动态规划的五部曲
1确定dp数组的含义下标的含义
2确定递推公式
3确定dp数组如何初始化
4确定遍历顺序
5打印dp数组用来debug
1到第ij位置有dp[i][j]的方法
2dp[i][j] dp[i - 1] dp[i][j - 1];
3dp数组初始化dp[0][j] 1,dp[i][0] 1;
4从上向下从左向右遍历
5打印dp数组可以用来debug
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 i 0; i n; i) dp[0][i] 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 代码随想录 视频讲解动态规划这次遇到障碍了| LeetCode63. 不同路径 II_哔哩哔哩_bilibili 看完代码随想录之后的想法
我们要知道动态规划的五部曲
1确定dp数组的含义下标的含义
2确定递推公式
3确定dp数组如何初始化
4确定遍历顺序
5打印dp数组用来debug
这道题和上一个几乎一样当我们遇到障碍的时候我们的dp[i][j] 0;
然后在初始化的时候我们遇到障碍之后我们障碍之后需要设置为0
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] dp new int[m][n];for(int i 0; i m obstacleGrid[i][0] 0; i) dp[i][0] 1;for(int i 0; i n obstacleGrid[0][i] 0; i) dp[0][i] 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];elsedp[i][j] 0;}}return dp[m - 1][n - 1];}
} 总结
昨天晚上没有做什么今天做了两道动态规划的题上午背了一下单词下午去买了一辆自行车
呜呜呜没钱了
