整数拆分问题动态规划c语言

整数拆分问题是指将一个正整数n拆分成若干个正整数的和，求拆分后各个正整数的乘积的最大值。例如，当n=10时，将其拆分为3+3+4，其乘积最大为36。

下面是使用动态规划算法求解整数拆分问题的C语言代码：

#include <stdio.h>

#define MAXN 100    //最大拆分数

int dp[MAXN];    //记录拆分后各个数的最大乘积

int max(int a, int b)
{
    return (a > b) ? a : b;
}

int main()
{
    int n, i, j;

    //读入正整数n
    printf("请输入正整数n：");
    scanf("%d", &n);

    //初始化dp数组
    dp[1] = 1;

    //动态规划求解
    for (i = 2; i <= n; i++)
    {
        for (j = 1; j < i; j++)
        {
            dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]));
        }
    }

    //输出结果
    printf("拆分后各个正整数的最大乘积为：%d\n", dp[n]);

    return 0;
}

其中，dp[i]表示将正整数i拆分后各个正整数的最大乘积。在动态规划求解时，对于正整数i，从1到i-1遍历所有可能的拆分情况j和i-j，其中，j*(i-j)表示将i拆分为j和i-j两个数的乘积，j*dp[i-j]表示将i拆分为j和i-j两个数以及i-j拆分后各个正整数的最大乘积的乘积。最终，dp[n]即为将正整数n拆分后各个正整数的最大乘积。