一种硬币交换变量的动态规划

Question

我对解决硬币交换问题的一种变体感兴趣。回想一下硬币交换问题的正式定义：

给定一个值N，如果我们想改变N分，并且我们有无穷多的S={S1，S2，…，Sm}整值硬币，我们有多少种方法可以改变？硬币的顺序无关紧要。例如，对于N=4和S={1,2,3}，有四种解决方案：{1,1,1}，{1,1,2}，{2,2}，{1,3}。所以输出应该是4。对于N=10和S={2,5,3,6}，有五个解：{2,2,2,2,2}，{2,2,3,3}，{2,2,6}，{2,3,5}和{5,5}。所以输出应该是5。请参阅此处了解更多详细信息。

在这里，可以找到一个基于表格DP的解决方案。此解决方案基于以下递推关系：

count(S, m, n) = count(S, m - 1, n) + count(S, m, n - S[m - 1]);

与基本情况：

count(S, m, n < 0) = 0
count(S, m, n = 0) = 1
count(S, m <= 0, n >= 1) = 0

直观地说，这种递归关系将一个问题定义为两个子问题的解决方案：一个是我们丢弃硬币的问题，另一个是我们假设硬币一次使用一次的问题。

问：我如何修改这个递归关系来计算我们可以不考虑顺序和偶数个求和的求和方式的数量？例如，对于N=4和S={1,2,3}，共有四个解（不考虑顺序）：{1,1,1,1}，{1,1,2}，{2,2}，{1,3}，但其中只有3个求和数为偶数，即{1,1,1,1}，{2,2}，{1,3}。

先前的研究：首先，我认为我可以在丢弃硬币的情况下将请求的金额翻倍，并要求在我们将使用部分硬币的情况下，每枚硬币消费两次，即：

count(S, m, n) = count(S, m - 1, 2*n) + count(S, m, n - 2*S[m - 1]);

这适用于一些示例案例，但不起作用。有什么提示吗？

Answer 1

您需要在递归中添加一个标志，它是到目前为止使用的求和数的奇偶校验。

使用求和键时，翻转标志（S（n-v[m]，m，！奇偶校验））。

基本案例是：

n=0 parity=0 -> 1

n=0 parity=1 -> 0

n<0 or m<0 (array is 0-indexed) -> 0

下面是c中的递归函数。当然，你需要把它记下来，这样它才能产生更大的价值。

int S(int n,int m,bool parity)
{
    if (n==0)
    {
        if (parity==1)
            return 0;
        else 
            return 1;
    }
    if (m<0 || n<0)
        return 0;
    return S(n,m-1,parity)+S(n-v[m],m,!parity);
}