LeetCode <dp>62&63.Unique Paths I&II
原创LeetCode <dp>62&63.Unique Paths I&II
原创
62.Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 7 x 3 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right题目大意：问有多少种走法
解法一：
采用递归形式的解法，这是一个典型的动态规划问题,采用记忆化搜索法。
public int uniquePaths(int m, int n) {
int [][] mem = new int[m+1][n+1];
return helper(m,n,mem);
}
public int helper(int m, int n,int [][] mem){
if (m == 1|| n ==1){
return 1;
}
if (mem[m][n] ==0){
mem[m][n] = helper(m-1,n,mem)+helper(m,n-1,mem);
}
return mem [m][n];
}解法二：
非递归形式的解法。
public int uniquePaths(int m, int n) {
int [][] mem = new int[m][n];
for (int i = 0;i<m;i++){
for (int j = 0;j<n;j++){
if (i==0||j==0){
mem[i][j] = 1;
continue;
}
if (mem[i][j] == 0) {
mem[i][j] = mem[i][j-1]+mem[i-1][j];
}
}
}
return mem[m-1][n-1];
}解法三：
解法一与解法二没有本质的区别，就是递归与非递归的区别，解法三采用的是一维的滚动数组，压缩存储中间量的空间。
public int uniquePaths(int m, int n) {
int [] mem = new int[n+1];
mem[1] =1;
for (int i = 0;i<m;i++){
for (int j = 1;j<=n;j++){
mem[j] = mem[j-1]+mem[j];
}
}
return mem[n];
}
}63.Unique Paths II
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
Note: m and n will be at most 100.
Example 1:
Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right题目大意：矩阵中1代表障碍物，问有多少中走法。
解法：
思路：采用的一维空间的数组解决。
* obstacleGrid = 0,0,0
* 0,1,0
* 0,0,0
* index of dp 0,1,2,3
* first time 0,1,1,1
* sec time 0,1,0,1
* third time 0,1,1,2
*
* ******************
* obstacleGrid = 0,0,0
* 0,0,0
* 0,0,0
* index of dp 0,1,2,3
* first time 0,1,1,1
* sec time 0,1,2,3
* third time 0,1,3,6解法如下：
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int [] dp = new int[n+1];
dp[1]=1;
for (int i = 0;i<m;i++){
for (int j = 1;j<=n;j++){
if (obstacleGrid[i][j-1] ==1){
dp[j] = 0;
}else {
dp[j] += dp[j-1];
}
}
}
return dp[n];
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。