51nod 1201：整数划分超级好的DP题目

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。

Input

输入1个数N(1 <= N <= 50000)。

Output

输出划分的数量Mod 10^9 + 7。

Input示例

Output示例

这个DP想得真叫我累啊，还想不出来。后来问了夹克老师，发现这个DP真是经典啊。

用dp[i][j]表示j个数组成i的个数。那么对于dp[i][j]每一个j来说，注意是对于每一个j来说，来源就是两个，一个就是插入j时的dp[i-j][j-1]个数。

然后就是因为要不同整数，不同的来源在哪里，就是将[i-j][i](其含义是i个数组成了i-j)中的每一个数加1，这点这是奇妙啊，就组成了dp[i][j]的剩余部分。

所以dp[i][j]=dp[i-j][i]+dp[i-j][i-1]

这个题真是好题。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

const int maxn = 50000 + 100;

const int mod = 1e9 + 7;

int dp[maxn][350];

int main()

{

	//freopen("i.txt","r",stdin);

	//freopen("o.txt","w",stdout);

	int n;

	scanf("%d", &n);

	dp[0][0] = 1;

	for (int i = 1; i<7; i++)

	{

		for (int j = 0; j <= n; j++)

		{

			if (j - i >= 0)

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

		}

	}

	int ans = 0;

	for (int i = 1; i<350; i++)

		ans = (ans + dp[n][i]) % mod;

	cout << ans << endl;

	return 0;

}

巴特西

51nod 1201：整数划分超级好的DP题目

最新文章

热门文章

巴特西

51nod 1201：整数划分 超级好的DP题目

最新文章

热门文章

51nod 1201：整数划分超级好的DP题目