给定一个正整数 n,找出将 n 分成四份或将 n 表示为四个正整数之和的方法数。这里的 n 从 0 到 5000 不等。
def foo(target, k, j):
count = 0
map = {}
if target in map.keys() and map[target] == k:
return map[target]
if target == 0 and k == 0:
return 1
if target <= 0 or k < 0:
return 0
for i in range(j, target+1):
count += foo(target-i, k-1, i)
map[target] = count
return count
print(foo(10, 4, 1))
我已经用上面的递归解决方案解决了这个问题,但我只是看到有人用下面的动态规划解决方案。
f(0,0) = 1
f(target, k) = 0 如果 k > target 或 (target > 0 and k = 0)
f(目标, k) = f(目标-k, k) + f(目标-1, k-1)
有人可以启发我这个解决方案吗?
最佳答案
这个解决方案是正确的,但有点棘手,我会尽力向您解释清楚。
如果target=25
,我们将其拆分为25=9+7+5+4
。我们用4列(1*9、1*7、1*5、1*4)表示:
但换个角度看,你可以把图像看成9行(1*4, 1*4, 1*4 , 1*4, 1*3, 1*2, 1*2, 1*1, 1 *1).
因此,您会发现您的解决方案是按列构建图像,而该解决方案是按行构建图像。
因此我们来了解该解决方案的详细信息:
- f(目标, k) = f(目标-k, k) + f(目标-1, k-1)
- f(target, k):保留
target
个方 block ,行的长度为k
- f(target - k, k): 放一行长度
k
- f(target - 1, k - 1):只将一个方 block 放在最右边的列(确保答案是正整数),并将行的长度减少 1。
就这些。
如果您还有任何问题,可以在这里发表评论。
关于algorithm - 计算将数字分成 4 部分的方法数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33992647/