279. 自然数拆分（完全背包）

本文主要是介绍279. 自然数拆分（完全背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个自然数N，要求把N拆分成若干个正整数相加的形式，参与加法运算的数可以重复。

求拆分的方案数 mod 2147483648的结果。

输入格式
一个自然数N。

输出格式
输入一个整数，表示结果。

数据范围
1≤N≤4000
输入样例：
7
输出样例：
14

思路： 因为可以重复选，所以上一步的状态得是选过的。

#include <cstdio>
#include <cstring>using namespace std;const int maxn = 10000 + 7;
const int mod = 2147483648;
typedef long long ll;
ll dp[maxn];//The value when the sum it i.
int main()
{int n;scanf("%d",&n);dp[0] = 1;for(int i = 1;i <= n;i++){for(int j = i;j <= n;j++){dp[j] += dp[j - i];dp[j] %= mod;}}printf("%lld\n",(dp[n] - 1) % mod);return 0;
}

这篇关于279. 自然数拆分（完全背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---