递归实现整数拆分数函数的原理及memo数组作用解析

嘿，我来帮你把这个递归函数的逻辑掰明白，尤其是你困惑的memo数组到底在干嘛～

先搞懂memo[n]和memo[n][m]是什么 #

这个memo是记忆化缓存数组，用来存已经计算过的结果，避免重复递归浪费时间。它是一个数组的数组（模拟二维数组）：

• memo[n]是一个子数组，专门存和整数n相关的拆分结果
• memo[n][m]表示的是：拆分整数n时，所有拆分项都不超过m的拆分方式总数

举个例子：memo[3][2]就是拆分3时，拆分项最大只能是2的方式数——也就是1+1+1、1+2这两种，所以值是2。

递归函数的核心逻辑拆解 #

先看函数定义：function sum(n, m = n)，默认m等于n，因为拆分n的时候，最大的拆分项最多就是n本身（比如直接拆成n这一种）。

函数里的几个分支：

1. if (n == 0) return 1：这是递归的终止条件之一，意思是“我们已经把n完全拆分完了，这是一种有效的拆分方式”。比如拆分3时，用了一个3，剩下的数是0，说明这是一个有效拆分，算1种。
2. if (n < 0 || m == 0) return 0：n<0说明拆过头了（比如用3去拆2，剩下-1，无效）；m==0说明没有可用的拆分项了，凑不出n，所以这两种情况都返回0种。
3. if (memo[n] && memo[n][m]) return memo[n][m]：这就是记忆化的核心——如果之前已经计算过sum(n,m)的结果，直接返回缓存的值，不用再递归计算，节省时间。

最关键的递归公式：total = sum(n, m - 1) + sum(n - m, m) #

这个公式是整个逻辑的灵魂，拆成两部分理解：

• sum(n, m - 1)：表示不使用m作为拆分项的所有方式数。也就是拆分n时，最大拆分项只能是m-1的总数。比如计算sum(3,3)时，这部分就是sum(3,2)——也就是不拆出3的那些方式（1+1+1、1+2）。
• sum(n - m, m)：表示至少使用一次m作为拆分项的所有方式数。因为已经用了一个m，剩下需要拆分的数是n-m，而且剩下的拆分项还可以继续用m（允许重复拆分，比如拆分4时用2，能拆成2+2）。比如sum(3,3)里这部分就是sum(0,3)，直接返回1，对应拆成3的这种方式。

把这两部分加起来，就是拆分n且最大项≤m的总方式数。

用sum(3)的例子走一遍，看memo怎么从空数组填充完整 #

我们调用sum(3)，默认m=3，一步步看：

1. 一开始memo是空的，不满足缓存条件，进入计算：
   total = sum(3,2) + sum(0,3)
   • sum(0,3)直接返回1，先记下来。
   • 计算sum(3,2)：
     同样没有缓存，继续拆：total = sum(3,1) + sum(1,2)
     • 先算sum(3,1)：
       无缓存，拆成sum(3,0) + sum(2,1)
       • sum(3,0)返回0；
       • sum(2,1)继续拆：sum(2,0) + sum(1,1)
         • sum(2,0)返回0；
         • sum(1,1)拆成sum(1,0) + sum(0,1)，返回0+1=1，然后把memo[1][1] = 1；
           所以sum(2,1)=0+1=1，把memo[2][1] = 1；
           最终sum(3,1)=0+1=1，把memo[3][1] = 1；
     • 再算sum(1,2)：
       无缓存，拆成sum(1,1) + sum(1-2,2)，也就是1 + 0 =1，把memo[1][2] =1；
       所以sum(3,2)=1+1=2，把memo[3][2] =2；
2. 回到sum(3,3)，total=2+1=3，把memo[3][3] =3，返回3。

最后memo的结构大概是这样（空项是未赋值的索引）：

memo = [
  , // index 0 未使用
  [ , 1, 1 ], // memo[1][1]=1，memo[1][2]=1
  [ , 1 ],    // memo[2][1]=1
  [ , 1, 2, 3 ] // memo[3][1]=1，memo[3][2]=2，memo[3][3]=3
]

为什么初始memo是空数组也能得到正确结果？ #

因为递归是自底向上填充memo的：每次遇到新的(n,m)组合，我们都会先递归计算它依赖的更小的(n,m)组合，把那些结果先存到memo里，再计算当前的结果并存进去。比如计算sum(3,3)之前，会先算sum(3,2)，而sum(3,2)又依赖sum(3,1)和sum(1,2)，这些更小的组合都会被先计算并缓存，所以不会出现找不到值的情况，最后一步步往上得到最终结果。

内容的提问来源于stack exchange，提问作者Ckate