题解

点个赞吧

题目大意

在方格中只能往右或下走，有几种不同路线走到右下角

解题思路

假设能有一种状态 f[i][j] 表示从 (1, 1) 到达 (i, j) 不同路径的总量。那么 m*n 的网格从 (1, 1) 到达 (m, n) 不同路径的总量，就是
f[m][n]。根据题意 f[i][j] 作为一次阶段性终点，它只能：
从上面来：f[i-1][j] 向下走
从左边来：f[i][j-1] 向右走
递推：f[i][j]=f[i-1][j]+f[i][j-1]

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
long long f[N][N];
int main(){
    int n,m;
    cin>>n>>m;
    //初始化：第一行和第一列
    f[1][1]=1;
    for(int i=1;i<=m;i++) f[1][i]=1;
    for(int i=1;i<=n;i++) f[i][1]=1;
    //递推：f[i][j]=f[i-1][j]+f[i][j-1]
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            f[i][j]=f[i-1][j]+f[i][j-1];
        }
    }
    cout<<f[n][m];
    return 0;
}