Leetcode-day30-动态规划-不同路径
62. 不同路径
这个题动态规划的特征比较明显，我们就看终点，到终点的不同路径就等于要么从他上面一格往下走一格，要么从他左边一个往右走一格，所以可以得出递推公式。
动态规划五部曲：
1. 确定dp数组的含义，这里是到达i,j的不同路径数
2.确定递推公式，dp[m][n] = dp[m-1][n]+dp[m][n-1]
3.dp初始化，这里是第一行初始化和第一列初始化，都是1
4.遍历方向，从上往下从左到右，根据递推公式得出来的，或者从左往右，从上到下。
5.打印dp数组，这里打印出终点位置的dp数组值就可以。
class Solution {public int uniquePaths(int m, int n) {//1. DP数组,到达第i,j有多少条不同的路径int[][] dp = new int[m][n];//2.递推公式： dp[m][n] = dp[m-1][n]+dp[m][n-1]//3.dp数组初始化：for(int i=0;i<m;i++){dp[i][0]=1;}for(int i=0;i<n;i++){dp[0][i]=1;}//4.遍历方向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
这个题和上个题类似，首先可以确定用动态规划来做，然后按照五部曲
1. dp数组代表什么，i,j坐标下的不同路径数
2.递推公式，dp[m][n] = dp[m-1][n]+dp[m][n-1]
3.dp数组初始化，和上一题不同的是第一行，或者第一列，如果中间已经有障碍那后面就都是0。
4.遍历方向，还是和上一题一样，不一样的是如果遇到障碍就直接这个位置置0，continue，不需要递推
5.打印dp数组。打印终点的dp值
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<n;i++){if(obstacleGrid[0][i]==1){break;}dp[0][i]=1;}for(int i=0;i<m;i++){if(obstacleGrid[i][0]==1){break;}dp[i][0]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==1){dp[i][j]=0;continue;}dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}