也买酒技术网站建设,访问数据库的网站开发语言,有谁知道知乎网站是谁做的,云点wordpress62.不同路径 初始思路#xff1a;
1#xff09;确定dp数组以及下标的含义#xff1a; dp[i][i]存放到第i1行和第i1列的方法数
2#xff09;确定递推公式#xff1a; dp[i][i] dp[i -1][i] dp[i][i-1]
3#xff09;dp数组如何初始化 第0行是1#xff1b; 第0列是1
1确定dp数组以及下标的含义 dp[i][i]存放到第i1行和第i1列的方法数
2确定递推公式 dp[i][i] dp[i -1][i] dp[i][i-1]
3dp数组如何初始化 第0行是1 第0列是1
4确定遍历顺序
从前到后
5举例推导dp数组
class Solution {public int uniquePaths(int m, int n) {int[][] dp new int[m][n];for(int i 0;im;i){dp[i][0] 1;}for(int i 0;in;i){dp[0][i] 1;}for(int i 1;im;i){for(int j 1;jn;j){dp[i][j] dp[i][j-1] dp[i-1][j];}}return dp[m-1][n-1];}
}
题解复盘 基本一致 。 63. 不同路径 II
初始思路
在前一题的基础之上增加了对障碍数组的判断如果第一行中有一个障碍那么这个障碍后面的dp全部赋值为0前面的都赋值为1列同理。
再过程中遇到障碍令当前dp为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;im;i){if(obstacleGrid[i][0]1){break;}dp[i][0] 1;}for(int i 0;in;i){if(obstacleGrid[0][i]1){break;}dp[0][i] 1;}for(int i 1;im;i){for(int j 1;jn;j){if(obstacleGrid[i][j]1){dp[i][j] 0;}else{dp[i][j] dp[i][j-1] dp[i-1][j];}}}return dp[m-1][n-1];}
}
