By

文章目錄

整数划分说的是给定一个正整数N，求一共有多少种方式将N分解成不超过N的正整数和。
例如：N=4时，一共有5种划分，如下：
4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
4 = 1 + 1 + 1 + 1

如果没记错的话，在《C名题精选百则》中出现过这题。我们可以考虑更普遍的情况，将正整数N分解成不超过M的整数和的情况。
对于这种情况，可以将分解分成包含整数M和不包含整数M的情况。令f(N,M)为总共的分解方式，则
f(N,M) = f(N - M, M) + f(N, M -1)，于是写成程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def partition(n):
    return _partition(n, n)

def _partition(n, m):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if m == 1:
        return 1
    else:
        return _partition(n - m, m) + _partition(n, m - 1)
for i in xrange(1, 10):
    print i, partition(i)

只是当n比较大时，递归的效率太慢了，于是用动态规划重写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def partition(n):
    dp = [[0 for i in xrange(n + 1)] for j in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][1] = 1
        dp[0][i] = 1
    for i in xrange(1, n + 1):
        for j in xrange(1, n + 1):
            if i - j >= 0:
                dp[i][j] = dp[i - j][j] + dp[i][j - 1]
            else:
                dp[i][j] = dp[i][j - 1]
    return dp[n][n]

for i in xrange(1, 10):
    print i, partition(i)

打赏作者

文章目錄