思路
其实这是一道非常经典的分苹果问题：
有m个一样的苹果和n个一样的盘子，把苹果放盘子里，每个盘子允许0-m个苹果，求问有多少种分法？
与本题的共通之点在于，输入的正整数可以看成m个苹果，拆分出的加数个数可以看成n个盘子，例如：4 = 1 + 1 + 3，可以看成4个苹果分到3个盘子中的一种情况。
为了更好地理解，我们继续回到分苹果问题上。
我们假设分苹果的结果由这样一个函数得出：f（m, n）
思考一种特殊情况：如果只有1个苹果，或者只有1个盘子，无论怎么折腾是不是只有1种分法？
至此我们就轻松找到了递归解法的出口，也找到了动态规划的base。
但是注意，我们这里原题是拆分整数，理论上整数可以为0，拆分的个数也可以为0，我们把这种情况也划分进去（主要是为了更方便处理动态规划的数组，后面会说），转换成代码即为：
if m <= 1 or n <= 1:f(m,n) = 1;
再考虑m<n的情况，盘子比苹果多得多，那我把多余的盘子拿走也不会有任何影响：
if m < n:f(m,n) = f(m, m)
再考虑最后一种情况m>=n，苹果比盘子多或者和盘子一样多，可以由2种场景涵盖：
①不存在空盘子。我先把每个盘子都放上1个苹果，就不存在空盘子啦，然后继续分我的苹果：
f(m - n, n)
②存在空盘子。有空盘子存在，换种说法至少让1个盘子为空，那我先把这个空盘子拿出来，然后继续分我的苹果：
f(m, n - 1)
以上2种情况转换为代码即为：
if (m >= n):f(m, m) = f(m - n, n) + f(m, n - 1)
最后这种情况为啥能等效，可能要花点力气去理解。
代码
现在我们可以开始撸代码了，先上递归解法：
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int num = sc.nextInt();System.out.println(cal(num, num));}}private static int cal(int m, int n) {if (m <= 1 || n == 1) {return 1;}if (m < n) {return cal(m, m);} else {return cal(m - n, n) + cal(m, n - 1);}}}
但是递归解法自顶向下，效率很低，如果画一下递归调用栈，会发现存在大量的重复计算，提交也会超时。。。
这时候就可以用动态规划来解，同样的思路，只不过是反过来自底向上。
用一个二维数组来存放每次的计算结果，以方便复用，而这个数组的base就是当i、j小于等于1的时候，arr[i][j]=1：
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int num = sc.nextInt();System.out.println(dp(num, num));}}private static int dp(int m, int n) {int[][] arr = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i <= 1 || j <= 1) {arr[i][j] = 1;} else if (i < j) {arr[i][j] = arr[i][i];} else {arr[i][j] = arr[i - j][j] + arr[i][j - 1];}}}return arr[m][n];}}
提交一下，完美通过。