1.822. 走方格 - AcWing题库

每次往右或者往下走一个单位距离
从左上角走到右下角有多少种不同的走法?
这道题可以用dp解决
定义dp数组 => dp[N][N]的含义就是 => 走到坐标为n,n有多少种走法
不难知道,
除了第一行第一列以外,所有数据都可以由走到该位置左边的数据加上走到该位置上边的数据递推出来
即 dp[n][n] = dp[n-1][n] + dp[n][n-1]

注意这题要求的是从格子的边线走所以2行3列实际上是3行4列

#include<iostream>

using namespace std;

const int N =15;
int dp[N][N];

int main(){
    int n,m;
    cin >> n >> m;

    //初始化
    for(int i=0; i<=m; i++)dp[0][i]=1;

    for(int i=0; i<=n; i++)dp[i][0]=1;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }

    cout << dp[n][m];

    return 0;

}