文章目錄

整数划分说的是给定一个正整数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)

文章目錄