Count Partitions(整数划分)

问题描述：

思路：

基本情况（Base case）

• 当n = 0时， 仅有 0 = 0一种划分，返回1
• 当n < 0时， 递归过界，返回0
• 当k = 0时， 无法划分，返回0

递推方法(Recursive calls)

• Q(n,m)=Q(n,m-1)+Q(n-m,m)
  等式右边第一部分Q(n,m-1)表示被加数不包含m的分划的数目，第二部分表示被加数中包含（注意不是小于）m的分划的数目，因为如果确定了一个分划的被加数中包含m,则剩下的部分就是对n-m进行不超过m的划分。

代码如下：

def count_partitions(n, k):
    """
    >>> count_partitions(5, 3)
    5
    >>> count_partitions(6, 4)
    9
    """
    if n == 0:
        return 1
    elif n < 0 or k == 0:
        return 0
    else:
        return count_partitions(n , k - 1) + count_partitions(n - k, k)

测试：

$ python3 -m doctest count_partiton.py -v
Trying:
    count_partitions(5, 3)
Expecting:
    5
ok
Trying:
    count_partitions(6, 4)
Expecting:
    9
ok
1 items had no tests:
    count_partiton
1 items passed all tests:
   2 tests in count_partiton.count_partitions
2 tests in 2 items.
2 passed and 0 failed.
Test passed.

递归树：