数的拆分，算法，动态规划，

数的拆分
一个正整数，可以拆分成若干个正整数的和。例如3可以拆成1+1+1，也可以拆成1+2。对于3，只有这2种拆分方法。
请编写程序，给定正整数n，计算其拆分方案数。
输入格式:
一个正整数n, n <= 5000。
输出格式:
拆分方案数。由于这个数字可能非常大，输出其对1000000007取模。

输入样例:
3
输出样例:
2

自然数拆分（回溯法）_进击的猴子wa的博客-CSDN博客_自然数拆分算法 一个整数N(N > 1)可以拆分成若干个大于等于1的自然数之和，请你输出所有不重复的拆分方式。若满足集合A=B，则称这两种拆分方式是重复的。例如 6 = 3 + 2 和 6 = 2 + 3, 就是重复的拆分方式。输入格式:一个正整数N（1≤N≤52）。注意：本题N的上限52，是经过PTA平台服务器测试后得到的上限，能够保证较好的搜索策略在PTA提交，在1s内求解。本地PC机上，即使较好方法运行时间也可能大于1s，如果觉得方法没问题，可以先提交试试。输出格式:按照拆分方案的字典序由小大到大 https://blog.csdn.net/qq_15740137/article/details/106081712

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int p(int n, int m)
{
    if (m == 1 || n == 1)
        return  1;
    if (n == m)
        return p(n, m - 1) + 1;
    if (n < m)
        return p(n, n);
    else
        return p(n, m - 1) + p(n - m, m);
}

int main()
{    
    printf("输入整数n:");
    int n;
    scanf("%d",&n);
    printf("有%d种划分方式", p(n, n));
}

参考
https://blog.csdn.net/burse_liu/article/details/122796122

你题目的解答代码如下：

#include <stdio.h>
long long int count(int n, int m)
{
    long long int a = 0;
    if (n <= 1 || m <= 1)
    {
        if (n < 1 || m < 1)
        {
            a = 0;
        }
        else if (n == 1 || m == 1)
        {
            a = 1;
        }
    }

    else
    {
        if (n < m)
        {
            a = count(n, n);
        }
        else
        {
            if (n == m)
            {
                a = count(n, m - 1) + 1;
            }
            else
            {
                a = count(n - m, m) + count(n, m - 1);
            }
        }
    }
    return a;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", count(n, n - 1)%1000000007);
    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!

采纳就对了

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        for(int i = 2; i <= n; i++) {
            int curMax = 0;
            for(int j = 1; j < i; j++) {
                curMax = max(curMax, max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        
        return dp[n];
    }
};