【递归+dp】杨辉三角

/* 杨辉三角：https://www.cnblogs.com/kevin-lee123/p/7096090.html */
/* 此类问题采用递归+dp，可以减少子问题重复计算的次数 */
#include <cstdio>
#include <iostream>
using namespace std;

int dp[1000][1000];

int YH(int m,int n){
    if(dp[m][n]!=0)    //dp思想：减少重复计算子问题
        return dp[m][n];
    else{
        if(n==0||m==n){
            dp[m][n]=1;
            return dp[m][n];
        }
        else{
            dp[m][n] = dp[m-1][n-1]+dp[m-1][n];
            return dp[m][n];
        }
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dp[i][j]=0;
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<=i;j++){
            if(j!=0)
                cout<<" ";
            cout<<YH(i,j);
        }
        cout<<"\n";
    }
    return 0;
}