题解 | 走方格的方案数

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

int uniquePaths(int m, int n) {
    // 创建DP表，dp[i][j]表示从(0,0)到(i,j)的路径数
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    // 初始化第一行：只能从左边来
    for(int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    
    // 初始化第一列：只能从上面来
    for(int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    
    // 状态转移：当前位置的路径数 = 上方 + 左方
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << uniquePaths(m+1, n+1) << endl;
    return 0;
}

// 64 位输出请用 printf("%lld")