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

Question

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

为此，我查看了硬币交换问题的典型实例:令S = [d_1, d_2, ..., d_m] 和n > 0 是请求的数量。除了 S 中的元素外，我们可以通过多少种方式将 n 相加？

如果我们按照动态规划方法为这个问题设计一个允许多项式复杂度的解决方案的算法，我们将首先研究这个问题以及它与更小和更小的问题之间的关系更简单的子问题。这将产生一个递归关系，该关系描述了根据相关子问题的解决方案表示问题的归纳步骤。然后，我们可以实现内存技术或制表技术，以在自上而下或底部有效地实现这种递归关系-up 方式，分别。

递归关系可能如下(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