整数划分问题动态规划C语言

整数划分问题是将正整数n表示成一系列的整数的和，n=n1+n2+…+nk(n1>=n2>=n3…nk>=1,k>=1)正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记为p(n)。动态规划是解决整数划分问题的一种常用方法。下面是一个使用动态规划解决整数划分问题的C语言程序：

#include <stdio.h>

int main()
{
int n, i, j;
printf("请输入正整数n：");
scanf("%d", &n);
int dp[n+1][n+1];
for(i=0; i<=n; i++){
for(j=0; j<=n; j++){
if(i==0 || j==0){
dp[i][j] = 0;
}
else if(i==1 || j==1){
dp[i][j] = 1;
}
else if(i<j){
dp[i][j] = dp[i][i];
}
else if(i==j){
dp[i][j] = dp[i][j-1] + 1;
}
else{
dp[i][j] = dp[i][j-1] + dp[i-j][j];
}
}
}
printf("正整数%d的划分数为：%d", n, dp[n][n]);
return 0;
}

该程序使用二维数组dp[i][j]表示将正整数i划分成不大于j的数的划分数。程序中使用了四个if语句来处理不同情况下的划分数，最终输出正整数n的划分数。