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

Question

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

为此，我正在研究硬币交换问题的规范实例：让S = [d_1, d_2, ..., d_m]和n > 0成为请求的数量。除了S中的元素之外，我们还能用多少种方法把n加起来呢？你知道吗

如果我们遵循动态规划的方法来设计一个算法来解决这个问题，这个算法将允许多项式复杂度的解决方案，我们将从研究这个问题以及它与更小更简单的子问题的关系开始。这将产生一个递归关系，该关系描述了一个归纳步骤，该步骤根据相关子问题的解来表示问题。然后我们可以实现记忆化技术或制表技术，分别以自上而下或自下而上的方式有效地实现这种递归关系。你知道吗

递归关系可以如下所示（Python3.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