博客

解题思路

这个题是比较简单的，举个例子就能明白，以样例输入3 7为例。

建立一个3*7的二维数组，初始时把首行和首列均赋为1，如下表所示。

之后把剩余的每行元素按从左到右的顺序遍历赋值，使其等于其左边元素和上边元素之和，表示从起点到当前位置的路径数，因为要到达该位置只能从上边或左边到来，赋值后如下表所示。

所以最终答案为28。

代码

#include<iostream>
using namespace std;
int uniquePaths(int m, int n) {
    if(m==1||n==1)  return 1;
    int a[m][n];
    for(int i=0;i<m;i++){
        a[i][0]=1;
    }
    for(int i=1;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];
}
int main(){
    int m,n;
    cin>>m>>n;
    cout<<uniquePaths(m,n)<<endl;
    return 0;
}