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

Question

我正在探索一种动态规划设计方法是如何与问题的基本组合特性相关联的。

为此，我将查看硬币交换问题的典型实例:让S = [d_1, d_2, ..., d_m]和n > 0成为请求的金额。我们可以用多少种方式将n加起来，只使用S中的元素

如果我们遵循动态规划方法来设计一个算法来解决这个问题，它将允许一个多项式复杂度的解，我们将从这个问题以及它与较小和更简单的子问题之间的关系开始。这将产生一个递归关系，它描述了一个归纳步骤，用相关子问题的解决方案来表示问题。然后，我们可以实现回传技术或制表技术，分别以自顶向下的或自下而上的方式有效地实现这种递归关系。

递归关系可以是以下内容(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