问个递归的问题,整数划分问题是将一个正整数n拆成一组数连加并等于n的形式,且这组数中的最大加数不大于n.如6的整数划分为
1个回答

这里的split(n,m),是最大加数不大于m的n的划分数.

还是以6的划分为例,当m=4时,观察上面列出的结果,实际上就是最大加数等于4的情况,加上最大加数小于4的所有情况.最大加数小于4的以split(n,m-1)表示,而最大加数等于4的划分数,实际上等于2的划分数.

这个稍微有点绕,但其实很好理解.最大加数已经确定了,那么无非就是n减去这个最大加数后的数有多少种划分的问题了,所以这里可能把它表示为split(n-m,m).

这里要注意的是第二个参数是m,而不是n-m,原因其实很简单,看m=2的时候的结果就很清楚了,这时虽然最大加数是2,要看6-2=4的划分数了,但因为最大加数已经是2,所以剩余的4的划分要限制最大加数不大于2.