题目描述

blablabla

样例

//基础课刷过，二刷感悟（从饼干题过来）
//有两种做法1背包，把已知总和是n，抽象为背包的容量；那么商品就是完全背包1，2，3;dpij就算i个j容量的解
//第二种；我觉得可以抽象为相对高度的排序；为有1和没有1；没有1的可以整体减去某个1；为什么：因为加1方案书不变
//相对高度不变；
//状态就算i个数字总和为j；最小值为1的可以通过i-1和j-1删除最小的一个1；和i-j；j整体减去1化成
//正确性解读，首先集合分为有1没1，不重步漏，其次；状态转移都可以由这两个状态转移过来
//不重不漏的集合
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n;
int dp[1010][1010];
// int main(){
//     cin>>n;
//     for(int i=0;i<=n;i++){
//         dp[i][0]=1;//一个也放不下
//     }
//     for(int i=1;i<=n;i++){
//         for(int j=0;j<=n;j++){
//             if(j>=i)
//             dp[i][j]=(dp[i-1][j]+dp[i][j-i])%mod;//放得下
//             else 
//             dp[i][j]=dp[i-1][j]%mod;//放不下；
//         }
//     }
//     cout<<dp[n][n]%mod;
// }
int main(){
    cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j>=i)
            dp[i][j]=(dp[i-1][j-1]+dp[i][j-i])%mod;
            else
            dp[i][j]=dp[i-1][j-1]%mod;
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res+=dp[i][n];
        res%=mod;
    }
    cout<<res;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla