不同路径 https://leetcode.cn/problems/unique-paths/description/

#include<bits/stdc++.h>
using namespace std;

int main(){
    int m,n;
    cin>>m>>n;
    // vector<vector<int>> dp(m+n,m+n);  错误！！！
    /*  m+n 表示外层 vector 的大小（即行数）。
        vector<int>(m+n) 表示每一行都是一个大小为 m+n 的 vector
    */
    vector<vector<int>> dp(m+n,vector<int>(m+n));

    //求C_{m+n-2}^{m-1}      总步数里，m-1步向右的路径数
    // 等价于  dp[m+n-2][m-1]

    // 两层遍历，生成杨辉三角
    for(int i=0;i<m+n;i++){
        for(int j=0;j<=i;j++){
            if(j==0 || j==i) dp[i][j]=1;
            else dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
        }
    }

    cout<<dp[m+n-2][m-1];

    return 0;
}