POJ1221 计算数的单峰回文分解 动态规划

这题有点难度，主要是考察动态规划，在网上查到一个解答摘录如下，d[pi][j] 表示将 i 分解为其中最大元素为 j 时有多少种分法。

还不是很理解，还要多想想。DP真是一个慢慢体会慢慢积累的过程。

//计算数的单峰回文分解
#include <iostream>
using namespace std;
int N;
typedef unsigned long long ull;
ull dp[460][460];
int M = 400;
void solve()
{
	int i,j;
	for (i = 0; i <= M;i++)
	{
		dp[i][i] = 1;
		dp[0][i] = 1;
	}
	for (i = 2; i <= M;i++)
		for (j = i -1;j > 0;j--)
		{
			ull temp = dp[i][j+1];
			if (i - 2*j == 0 || i - 2*j >= j)
			{
				temp += dp[i- 2*j][j];
			}
			dp[i][j] = temp;
		}
}
int main(){
	solve();
	while (scanf("%d",&N) != EOF && N)
	{
		printf("%d %lld/n",N,dp[N][1]);
	}
	return 0;
}