自然数拆分

题目 自然数拆分

image-2059c8aa

思路分析

可以理解成背包问题

怎么转变成呢

先举个例子 3可以拆分成 1 2吧 不能拆成0 3 因为最少要拆分成两个数个和 也就是说 在前3-1个物品里选 价值不超过3的选法的数量 变量变成了一个

用dp分析法来看

（直接画优化后的图了 优化后其实就是一个反过来的01背包 所以也就是选与不选两种）

image-2fe0ed33

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=4010;

long long mod=2147483648;

long long dp[N];

int n;

int main()

{

    cin>>n;

    dp[0]=1;//什么都不选也是一种选法

    for(int i=1;i<n;i++){

        for(int j=i;j<=n;j++){//完全背包 从小到大

            dp[j]=(dp[j]+dp[j-i])%mod;

        }

    }

    cout<<dp[n];

    return 0;

}

同类题型

视频讲解

⬅️ 整数拆分 🏠 00-刷题理模型 ➡️ 货币系统