题目描述: 给你一个正整数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])