题解 | #MT12 网格走法数目#(动态规划)

解题思路

1.注意走的是网格点,直接使用动态规划即可;

代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int m, n;
    while(cin >> m >> n){
        vector<vector<int>> f(m + 2, vector<int>(n + 2)); //注意走的是网格点
        f[1][1] = 1;
        for(int i = 1; i <= m + 1; i++){
            for(int j = 1; j <= n + 1; j++){
                if(i == 1 && j == 1) continue;
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
        cout << f[m+1][n+1] << endl;
    }
    return 0;
}