蓝桥杯 2022 dp 背包

蓝桥杯 2022 dp 背包

题目链接：

https://www.lanqiao.cn/problems/2186/learning/?subject_code=1&group_code=4&match_num=13&match_flow=2&origin=cup

题目：

 代码：

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

#define int long long

const int N = 5e5+5;

int dp[2023][11];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    dp[0][0]=1;   //取0个数字 总和为0的方案数
    
    //dp[i][j]表示取j个数字使得总和为i的方案数
    for(int i=1;i<=2022;i++){
        for(int j=1;j<=10;j++){
            if(i>=j) {  //保证下面下标有效为正
                dp[i][j]=dp[i-j][j]+dp[i-j][j-1];
            }
        }
    }    
    cout<<dp[2022][10];
    
    
    return 0;    

}