Leetcode-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 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

分析：此题第一眼想到就是DFS分别从右边格子和下边的格子各自探测然后得到结果

1         public int search(int m,int n,int cur_x,int cur_y){
2             if(cur_x == m-1 && cur_y == n-1){
3                 return 1;
4             }
5             if(cur_x > m-1 || cur_y > n-1){
6                 return  0;
7             }            
8              return search(m,n,cur_x,cur_y+1) + search(m,n,cur_x+1,cur_y);            
9         }

提交，超时，我擦

再想想，递归操作因为有回溯，会有重复探测重复计算的问题，效率低

换个写法

1         public int searchNew(int m,int n){
2             if(m == 1 || n == 1){
3                 return  1;
4             }            
5             return searchNew(m-1,n) + searchNew(m,n-1);
6

还是递归，只不过简洁了点，但是还是超时（递归没搞清楚啊，递归必然是有重复计算的问题）

那就DP填表吧，避免重复计算，分别从1*1的矩阵一直算到m*n，开个m*n的二维数组轻松搞定

但是---忽然想到这种只需要前一步结果的填表其实不需要矩阵，省点空间，开个一维数组保存上一步的结果就行了

 1         public int uniquePathsNew(int m,int n){
 2             int [] a = new int[n];                    
 3             for(int i = 0;i<n;i++){
 4                 a[i] = 1;
 5             }            
 6             for(int i=1;i<m;i++){
 7                 for(int j = 1;j< n;j++){
 8                     a[j] = a[j] + a[j-1];
 9                 }
10             }            
11             return a[n-1];
12         }

轻松AC