多种代币兑换的动态编程解决方案

我正在练习动态编程。我关注的是硬币兑换问题的以下变体：

I am practicing Dynamic Programming. I am focusing on the following variant of the coin exchange problem:

让 S = [1,2,6,12,24,48， 60] 是一组固定的整数硬币面额。假设 n 是通过 S 中的硬币可获得的正整数金额。考虑两个人 A 和 B 。我可以通过多种方式将 n 分配给 A 和 B ，以便每个人都能获得相同数量的硬币（不考虑每个人实际获得的货币数量）？

Let S = [1, 2, 6, 12, 24, 48, 60] be a constant set of integer coin denominations. Let n be a positive integer amount of money attainable via coins in S. Consider two persons A and B. In how many different ways can I split n among persons A and B so that each person gets the same amount of coins (disregarding the actual amount of money each gets)?

示例

n = 6 每人可以分为4种不同的方式：

n = 6 can be split into 4 different ways per person:

1. 人员 A 得到{2，2}，个人 B 得到{1 ，1}。


2. 人员 A 获得{2，1}，个人 B 得到{2，1}。


3. 人 A 得到{1，1}和人 B 得到{2，2}。


4. 人 A 得到{1，1，1}和一个人 B 得到{1，1，1}。

1. Person A gets {2, 2} and person B gets {1, 1}.
2. Person A gets {2, 1} and person B gets {2, 1}.
3. Person A gets {1, 1} and person B gets {2, 2}.
4. Person A gets {1, 1, 1} and person B gets {1, 1, 1}.

请注意每种方式是每人非冗余的，即我们不将{2，1}和{1，2}都视为两种不同方式。

Notice that each way is non-redundant per person, i.e. we do not count both {2, 1} and {1, 2} as two different ways.

先前的研究

我研究了非常相似的DP问题，例如硬币交换问题和分区问题。实际上，此站点中存在与几乎相同的问题有关的问题：

I have studied at very similar DP problems, such as the coin exchange problem and the partition problem. In fact, there are questions in this site referring to almost the same problem:

• 动态编程，用于代币兑换-在这里，OP研究递归关系，但引入时似乎有些困惑


• 硬币更改：动态编程 -在这里，OP似乎正在寻求解决方案的重建。


• 硬币更改（动态编程）-在这里，OP似乎也在寻求解决方案的重构。


• https://cs.stackexchange.com/questions/87230/用于多种变量的动态编程he-coin-exchange-problem -在这里，OP似乎在问一个类似的问题，但平价即分成两个人成为主要问题。

• Dynamic Programming for a variant of the coin exchange - Here, OP studies the recursion relationship, but seems confused introducing the parity constraint.
• Coin Change :Dynamic Programming - Here, OP seems to pursue the reconstruction of the solution.
• Coin change(Dynamic programming) - Here, OP seems to also pursue the reconstruction of the solution.
• https://cs.stackexchange.com/questions/87230/dynamic-programming-for-a-variant-of-the-coin-exchange-problem - Here, OP seems to ask about a similar problem, yet parity, i.e. splitting into two persons, becomes the main issue.

我主要对可以帮助我解决此问题的递归关系感兴趣。定义它将使我能够轻松地采用制表法的记忆来设计此问题的算法。

I am interested mostly in the recursion relation that could help me solve this problem. Defining it will allow me to easily apply either a memoization of a tabulation approach to design an algorithm for this problem.

例如，此递归：

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

  if n == 0:
    return 1

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

虽然很诱人，但却无法正常工作，因为执行时：

Is tempting, yet it does not work, because when executed:

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

以下是一个运行示例 S'= {1,2,6} 和 n = 6 ，是为了帮助我阐明模式（可能有错误）：

Here's an example of a run for S' = {1, 2, 6} and n = 6, in order to help me clarify the pattern (there might be errors):