algorithm - 使用小于或等于 k ​​的数字对数字求和的不同方法

Question

示例:给定 total = 8 且 k = 2，将 8 表示为 1 和 2 之间的整数之和的不同方式的数量为 5 种方式:

[1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 2, 2]
[1, 1, 2, 2, 2]
[2, 2, 2, 2]

约束:

1 <= total <= 1000
i <= k <= 100

我们如何解决这个问题？动态规划？

Answer 1

在面试中，如果您怀疑某个问题可能是动态规划，您应该立即将其编写为递归函数，然后添加缓存(又名内存)。

那么我们的基本情况是什么？

1. total 为 0。在这种情况下，一个空的总和就可以了。

2. total < 0，这样的话就没有办法了。

3. 我们正在考虑的数字范围是空的。那样的话就没有办法了。

在所有其他情况下，我们要么减小列表的大小，要么使用列表中的最大数量。

这个递归解决方案非常简单。

def ways_to_sum(total, lower, upper):
    if total < 0:
        return 0
    elif total == 0:
        return 1
    elif upper < lower:
        return 0
    else:
        return ways_to_sum(total - upper, lower, upper) + ways_to_sum(total, lower, upper - 1)

print(ways_to_sum(8, 1, 2)) # prints 5
print(ways_to_sum(800, 1, 5)) # locks up

现在的问题是我们一遍又一遍地做很多工作。因此我们添加缓存:

cached_ways_to_sum = {}
def ways_to_sum(total, lower, upper):
    if total < 0:
        return 0
    elif total == 0:
        return 1
    elif upper < lower:
        return 0
    else:
        key = (total, lower, upper)
        if key not in cached_ways_to_sum:
            cached_ways_to_sum[key] = ways_to_sum(total - upper, lower, upper) + \
                                      ways_to_sum(total, lower, upper - 1)
        return cached_ways_to_sum[key]

print(ways_to_sum(8, 1, 2)) # prints 5
print(ways_to_sum(800, 1, 5)) # prints 147624812

如果那时您被要求使用另一种方法来做到这一点，那么您才应该考虑采用自下而上的 DP 解决方案。即便如此，我也会考虑缓存中的内容并以此为基础进行构建。