题解 | 小红走矩阵

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
const long long N = 998244353;
//这个方法是是从拟合题目来写的，我们要找出状态转移方程,这里用最简单的方式来写
//所有的路径数量都来自他的上一步
//可以从上和左两条路来，所以所以就映出了dp[i][j]=dp[i-1][j]-dp[i][j-1]的状态转移方程
//但是要考虑边界，在i=0和j=0的时候这个方程会越界,这时候路径数来自上面或者左边
//于是方程变成了dp[i][j]=dp[i-1][j]和dp[i][j]=dp[i][j-1]这两种
//然后初始化起点为1
//在用if else来判断就可以算出了
//-----------------------------------------------
//这里可以预处理边界，让左边界和上边界全为1,从i=1,j=1开始
//这里预处理为一是因为在边界时候只有一条路径可以到达
//就不用判断是否在边界了,直接用推导出来的状态转移方程既可以了
int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>>dp(n, vector<ll>(m));
    //dp[i][j] = dp[i-1][j]+dp[i][j-1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) {
                dp[i][j] = 1;
            } else if (i == 0 && j != 0) {
                dp[i][j] = dp[i][j - 1] % N;
            } else if (i != 0 && j == 0) {
                dp[i][j] = dp[i - 1][j] % N;
            } else {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % N;
            }
        }
    }
    cout << dp[n - 1][m - 1] << endl;
    return 0;
}