class Solution {
public:
int uniquePaths(int m, int n) {
//自底向上，从最后一个节点的方案数向回计算
int a[1000][1000];
if(n ==1 || m==1){
return 1;
}
a[m][n] = 1;
for(int i = m ; i >=1 ;i-- ){
for(int j = n ; j >=1;j--){
if( i==m || j==n){
//一旦一条边已经达到边缘，方案数目就没有变化了
a[i][j] =1;
}
else{
a[i][j] = a[i][j+1] +a[i+1][j];
}
}
}
return a[1][1];
}
};
class Solution {
public:
//第二种从正向开始
int uniquePaths(int m, int n) {
int a[m][n];
for(int i = 0; i < m; i++){
a[i][0] = 1;
}
for(int i = 0; i < n; i++){
a[0][i] = 1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
a[i][j] = a[i-1][j]+a[i][j-1];
}
}
return a[m-1][n-1];
}
};
