题解 | #走方格的方案数#

走方格的方案数

走方格的方案数

/*
2022年09月21日 11:43:09
注意是沿着边缘线走，而不是在格子里走
并且只能往右或者往下走
n=1 m=1 右下、下右两种  --》n+m
n=1 m    1+m种  --》n+m
m=1 n    1+n种  --》n+m
m n大于1时，走到最后个格子右下角有2条路
右下、下右
递归实现即可
时间复杂度：OO(2^n)，其中n=max(m,n)，递归是一个树型递归
空间复杂度：O(n)，递归栈最大深度为树的深度nnn
*/

#include <iostream>
using namespace std;

int pathNum(int r, int c) {
    if (r == 0 || c == 0) // 不会有这种，至少得有一个格子才能走的
        return 0;
    if (r == 1 && c >= 1 || r >= 1 && c == 1)
        return r + c;
    return pathNum(r - 1, c) + pathNum(r, c - 1);
}

int main() {
    int row, col;
    cin >> row >> col;
    cout << pathNum(row, col) << endl;
}

/*
2022年09月21日 11:43:09
动态规划

用dp[i][j]表示到第i行第j列的方案数，
= 左边的方案数+上边的方案数
r=0 || c=0 其实就是一条横线或者竖线，只有一种方案

*/

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int r, c;
    cin >> r >> c;
    vector<vector<int>> dp(r+1, vector<int>(c+1, 0));
    for(int i = 0; i <= r; ++i){
        for(int j = 0; j <= c; ++j){
            if(i == 0 || j == 0) // 一条直线
                dp[i][j] = 1;
            else
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
        }
    }
    cout << dp[r][c] << endl;
}