# 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```

## 解法：

```    * 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];
}```

0 条评论

## 相关文章

１。Webservice中的方法重载问题 （１）在要重载的WebMethod上打个MessageName标签 比如: [WebMethod(Message...

19710

### Leetcode 213 House Robber II

Note: This is an extension of House Robber. After robbing those houses on that...

2098

741

1843

741

1521

### 聊聊storm的window trigger

storm-core-1.2.2-sources.jar!/org/apache/storm/trident/windowing/WindowTridentPr...

1310

### Codeforces 768B Code For 1

B. Code For 1 time limit per test:2 seconds memory limit per test:256 megabytes ...

3768

### 聊聊storm的maxSpoutPending

storm-2.0.0/storm-client/src/jvm/org/apache/storm/Config.java

2425

60210