LEET code -- 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.

是一個DP問題

事實上只要碰到1 就不要再算了  因為路只有一條

但是下面版本跑太慢了

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int uniquePaths(int m, int n) { int down=0,right=0; if(m==1 || n==1)return 1; //else if(m==1)right=uniquePaths(m,n-1); //else if(n==1)down=uniquePaths(m-1,n); else { right=uniquePaths(m,n-1); down=uniquePaths(m-1,n); } return right+down; } };

---------------
會慢是因為 這題可以用陣列寫完
所以recursive太慢

做 M*N的大小double vector
vector>   a(m,vector(n,0));

邊全部都是1  因為這些都是1步可以到的

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> ans(m,vector<int> (n,0) );//double vector for(int i=0;i<m;i++)ans[i][0]=1; for(int j=0;j<n;j++)ans[0][j]=1; for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ ans[i][j]=ans[i-1][j]+ans[i][j-1]; } } return ans[m-1][n-1]; } };