M04117: 简单的整数划分问题

dfs, dp, http://cs101.openjudge.cn/practice/04117/

思路：

• 设 $d{p}_{i,j}$ 表示把 $i$ 划分称若干正整数之和、且其中最大者为 $j$ 的方案数。
• 初值：$d{p}_{0,0}=1$。
• 转移：枚举次大者，可知 $d{p}_{i,j}={\displaystyle \sum _{k=0}^{j}d{p}_{i-j,k}}$。
• 答案：${\displaystyle \sum _{i=1}^{n}d{p}_{n,i}}$。
• 时间复杂度为 $O(N^3+\sum n)$，其中 $N=50$。
• 注意本题要多测！

代码：

#include <stdio.h>

const int N = 50;
int dp[N + 1][N + 1];

int main(){
	int n;
	dp[0][0] = 1;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= i; j++){
			for (int k = 0; k <= j; k++){
				dp[i][j] += dp[i - j][k];
			}
		}
	}
	while (scanf("%d", &n) != EOF){
		int ans = 0;
		for (int i = 1; i <= n; i++){
			ans += dp[n][i];
		}
		printf("%d\n", ans);
	}
	return 0;
}