pythonTip 94 整数划分

题目描述： 给你一个正整数N，请你求出一共有多少种方式用不超过N的正整数求和得到N。 例如： N=4，则输出5.因为4只有如下五种求和方式： 4 = 4 4 = 3 + 1 4 = 2 + 2 4 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1

示例： 输入： N = 1 输出： 1

分析:

整数划分问题。

设 nums[N][M] 表示 将 整数 N 分解为不超过 M 的数相加的方案数。则：

当 M == 1 或 N == 1 时，nums[N][1] = nums[1][M] = 1。

当 N == M 时， nums[N][M]= 1 + nums[N][M-1]。 这里的 “1” 就是， 4 = 4这种情况。

当 N < M 时， nums[N][M] = nums[N][N] 。 因为 不可能出现 4 = 5 这种可能。

当 N > M 时， nums[N][M] = nums[N][M-1] + nums[N-M][M] 这里是比较难理解的一步。

nums[N][M] = nums[N][M-1] + nums[N-M][M] 例如 N = 6, M = 4。也就是说，把整数 6 分解为不超过 4 的数相加的方案数，

可以分为两种，第一种是 不超过4 的，另外一个是包括4的。 如果包括4，那么就变成了 nums[2][4] 。如果不包括4 那就是 nums[6][3]。

所以 nums[6][4] = nums[6][3] + nums[2][4] 然后 nums[2][4] = nums[2][2] 再依次类推。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13

nums = [[0 for i in range(N+2)] for j in range(N+2)]

for i in range(1, N+1):
    for j in range(1, N+1):
        if i == 1 or j == 1:
            nums[i][j] = 1
        elif i == j:
            nums[i][j] = 1 + nums[i][j-1]
        elif i < j:
            nums[i][j] = nums[i][i]
        else:
            nums[i][j] = nums[i][j-1] + nums[i-j][j]
print(nums[N][N])