控制动态规划解决方案的组合方面

Question

我正在探索动态规划设计方法如何与问题的潜在组合属性相关联。

为此，我正在查看 硬币兑换问题 的规范实例：让 S = [d_1, d_2, ..., d_m] 和 n > 0 成为请求的数量。除了 S 中的元素外，我们可以通过多少种方式加起来 n？

如果我们遵循 动态规划 方法来为这个问题设计一个算法，该算法将允许具有多项式复杂度的解决方案，我们将从查看问题及其如何开始与更小和更简单的子问题有关。这将产生一个 递归关系 描述一个归纳步骤，该步骤根据相关子问题的解决方案来表示问题。然后我们可以实现 memoization 技术或 tabulation 技术以在 top-down[=] 中有效地实现这种递归关系90=] 或 自下而上 方式。

递归关系可能如下（Python 3.6 语法和基于 0 的索引）：

def C(S, m, n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if m <= 0:
        return 0
    count_wout_high_coin = C(S, m - 1, n)
    count_with_high_coin = C(S, m, n - S[m - 1])
    return count_wout_high_coin + count_with_high_coin

但是，在绘制子问题 DAG 时，可以看到任何实现此递归关系的基于 DP 的算法都会产生正确数量的解，但不考虑顺序。

例如，对于S = [1, 2, 6]和n = 6，可以通过以下方式识别（假设顺序很重要）：

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

假设顺序无关紧要，我们可以算出以下解决方案：

1. 1 + 1 + 1 + 1 + 1 + 1
2. 2 + 1 + 1 + 1 + 1
3. 2 + 2 + 1 + 1
4. 2 + 2 + 2
5. 6

从动态规划的角度解决问题时，如何控制顺序？具体来说，我怎么写函数：

• count_with_order()
• count_wout_order()

?

是否需要对顺序进行排序意味着选择修剪回溯而不是动态规划方法？

Answer 1

每个问题都是特殊的，尽管有些问题可以归为一类。对于您的特定示例，通过考虑 n 的解决方案数量等于每个较低可实现数量可实现的解决方案总数，即 n - coin 每个面额。

Python代码：

def f(n, coins):
  if n < 0:
    return 0

  if n == 0:
    return 1

  return sum([f(n - coin, coins) for coin in coins])

# => f(6, [1, 2, 6]) # 14