leetcode 62. Unique Paths

Seawolf

1. A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
   
2. 
   
3. 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).
   
4. 
   
5. How many possible unique paths are there?
   
6. 
   
7. 
   
8. Above is a 7 x 3 grid. How many possible unique paths are there?
   
9. 
   
10. Note: m and n will be at most 100.
    
11. 
    
12. Example 1:
    
13. 
    
14. Input: m = 3, n = 2
    
15. Output: 3
    
16. Explanation:
    
17. From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
    
18. 1. Right -> Right -> Down
    
19. 2. Right -> Down -> Right
    
20. 3. Down -> Right -> Right
    
21. Example 2:
    
22. 
    
23. Input: m = 7, n = 3
    
24. Output: 28

复制代码

DP：二维数组

1. class Solution {
   
2.     public int uniquePaths(int m, int n) {
   
3.         
   
4.         int[][] memo = new int[n+1][m+1];
   
5.         
   
6.         for(int i = 1; i<= n; i++){
   
7.             for(int j = 1; j<= m; j++){
   
8.                 memo[i][j] = 1;
   
9.             }
   
10.         }
    
11.         
    
12.         for(int i = 2; i<= n; i++){
    
13.             for(int j = 2; j<= m; j++){
    
14.                 if(i == 1 && j == 1) memo[i][j] = 1;
    
15.                
    
16.                 if((i == 1 && j != 1)) memo[i][j] = memo[i][j-1];
    
17.                 else if( (j == 1 && i!= 1)) memo[i][j] = memo[i-1][j];
    
18.                 else memo[i][j] = memo[i][j-1] + memo[i-1][j];
    
19.             }
    
20.         }
    
21.         
    
22.         return memo[n][m];
    
23.         
    
24.     }
    
25. }

复制代码

DP： 优化为一维数组

1. class Solution {
   
2.     public int uniquePaths(int m, int n) {
   
3.         
   
4.         int[] memo = new int[m+1];
   
5.         int former = 0;
   
6.         
   
7.         for(int j = 0; j<= m; j++){
   
8.             memo[j] = 1;
   
9.         }
   
10.         
    
11.         
    
12.         for(int i = 1; i<= n; i++){
    
13.             for(int j = 1; j<= m; j++){
    
14.                
    
15.                 if((i == 1 && j != 1)) memo[j] = memo[j-1];
    
16.                 else if( (j == 1 && i!= 1)) former = 1;
    
17.                 else {
    
18.                     memo[j] = memo[j] + former;
    
19.                     former = memo[j];
    
20.                 }
    
21.             }
    
22.         }
    
23.         
    
24.         return memo[m];
    
25.         
    
26.     }
    
27. }

复制代码