无法理解骰子滚动排列问题背后的逻辑

Question

我很难理解臭名昭著的"用n个掷骰子的k面找出达到给定和的总方法“问题背后的逻辑。在广泛寻找解释之后，我出现了空白。

我的困惑源于这样一个事实，即它似乎不遵循“用硬币进行改变的方法的数量”问题的逻辑，这一点在许多视频中得到了很好的解释，尤其是这 one。

我对硬币兑换问题的理解

我相信这是相当合理的。从本质上说，当我们越过第一排时，我们会从第一枚硬币和第二枚硬币，而不仅仅是第二枚硬币(一般来说，它是当前硬币加上所有以前的硬币)，来确定目标的数量。正如在链接视频中所解释的，我们需要遵循一些规则才能做到这一点：

If <the value of the coin is greater than the target>
     Simply copy the value from the cell above.  
Else
     a) Determine the number of ways we can make the target when we EXCLUDE the current coin
     b) Determine the number of ways we can make the target when we INCLUDE the current coin
     c) Add the two together and store the result in the cell.

对于步骤a，我们可以通过复制上面单元格中的值来确定这一点:毕竟，这是我们可以在没有当前硬币的情况下实现相同目标的方法的数量。对于3，我们复制0。这是正确的，使用2枚硬币，有0种方法使目标为3。

对于步骤b，我们需要从目标中减去当前的硬币，这将给出剩余的部分。然后，我们需要确定有多少种方法使这个剩余的钱从目前的硬币。因此，对于值3的变化，我们有(3-3)，即0。对于0的目标，有一种方法可以用三枚硬币制造0，如表所示(突出显示)。因此，我们有0+ 1 =1。

因此，我可以看到如何填充整个表。这里使用的算法并不重要。

我无法理解骰子问题逻辑

以下算法来自上述链接：

long findWays(int f, int d, int s) 
{ 
    // Create a table to store results of subproblems. One extra 
    // row and column are used for simpilicity (Number of dice 
    // is directly used as row index and sum is directly used 
    // as column index). The entries in 0th row and 0th column 
    // are never used. 
    long mem[d + 1][s + 1]; 
    memset(mem,0,sizeof mem); 
    // Table entries for no dices 
    // If you do not have any data, then the value must be 0, so the result is 1 
    mem[0][0] = 1; 
    // Iterate over dices 
    for (int i = 1; i <= d; i++) 
    { 
        // Iterate over sum 
        for (int j = i; j <= s; j++) 
        { 
            // The result is obtained in two ways, pin the current dice and spending 1 of the value, 
            // so we have mem[i-1][j-1] remaining combinations, to find the remaining combinations we 
            // would have to pin the values ??above 1 then we use mem[i][j-1] to sum all combinations 
            // that pin the remaining j-1's. But there is a way, when "j-f-1> = 0" we would be adding 
            // extra combinations, so we remove the combinations that only pin the extrapolated dice face and 
            // subtract the extrapolated combinations. 
            mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]; // CONFUSION POINT A
            if (j - f - 1 >= 0) 
                mem[i][j] -= mem[i - 1][j - f - 1];   // CONFUSION POINT B
        } 
    } 
    return mem[d][s]; 
} 

我已经一遍又一遍地读了这段代码，也许读了太多次了，但我就是不明白。

输入:骰子数(d) = 3，每个模具上的面数(f) = 3，目标值(s) = 3。我添加了一些调试输出，并生成了以下内容，以显示如何计算表中的单元格：

[1,1] = [1,0] + [0,0]
[1,2] = [1,1] + [0,1]
[1,3] = [1,2] + [0,2]

!! [2,1] is never calculated, CONFUSION POINT C !!

[2,2] = [2,1] + [1,1]
[2,3] = [2,2] + [1,2]

所以，把算法分解成简单的英语，这就说明了

the number of ways of making 3 with 2 dice [2,3] is
    the number of ways of making 2 with 2 dice [2,2] +
    the number of ways of making 2 with 1 die  [1,2]

此时，它似乎没有遵循硬币更改问题的逻辑；即，我上面发布的psuedo代码块。我甚至试着给出骰子数值来尝试应用这个逻辑；也就是说，模具1是1，而模具2是2,1，以遵循类似的“添加额外硬币”的想法，但它就是行不通。这让我感到担忧，因为虽然我理解动态规划背后的(美丽的)概念，但我似乎不能将相同的逻辑应用于所有类似的此类问题。

我的问题

有谁能解释一下我的三个困惑点：

( a)这是如何运作的，以及背后的逻辑。

( b)这条线到底在干什么？

( c)为什么从未计算过单元格2,1？我现在非常肯定，这只是因为我们永远无法从2骰子中得到1，但我想确认一下，万一我错过了什么。

Answer 1

这两种算法通常都是用递归，表示的，但是实际的实现通常使用迭代技术来完成--这有时会导致混淆，因为您所呈现的算法迭代地用期望的值填充一个表，然后返回我们要寻找的一个单元格中的值。

让我们详细地写出递归算法:我们想用F面的D骰子来表示和S的数N(D，S)，所有的面都是1.F.每个模都必须使用，所以我们可以立即说，对于所有D>，N(D，a)=0，即N(D，sum )表的左下半部都是零。同时，N(D，S) = 1，因为只有一种方法可以用D骰子滚动D(当所有的骰子都是1)，所以对角线是1。

所有递归都以一个基开始。有一种方法可以用1在1和F之间滚动任何数字，而对于所有其他数字则是不可能的：

1. N(1，S) =1表示所有S=1...F，N(1，S) =0

现在让我们来看一个D< S的任意N(D，S)，Dth模有一种表示j=1.F的任意j的方式，所以N(D，S)是所有N(D-1，So‘)的和，其中双叉模’在n-F和-1之间。

1. [中英文摘要] N(D，S) =和(N(D-1，S‘)，n(D，S)=和，n(D，S)=和(n(D，S)=和(N(D-1，S'))，n(D，S)= SUM(N(D-1，S’))。S-1

所以你基本上把水平条上的F数加到(D，S)的左上角。因此，对于任何D行，你都可以从上面的线推导出数字。重复这样做，直到到达第一行，而这已经完成了递归。

您提出的算法不是递归计算，而是迭代计算，并大量使用预先计算的数据。您注意到，在任何一点上，它都不实际将上面一行的F值相加，没有类似的循环。

    // Iterate over the values in the row above
    for (int k = j-f-1; k <= j-1; k++) 

它可以跳过这一点，因为左边单元格中的值已经有了几乎是这个值。特别是

N(D，S-1) = SUM(N(D-1，S''))，n(D，S-1)，n(D，S-1)=SUM(N(D-1，S'‘)，SUM(D，S-1)=SUM(D，S-1)=SUM(N(D-1，S’))，具有较好的性质.S-2

所以

N(D，S) = N(D，S-1) + N(D-1,1996-1)- N(D-1，F-1)

或用C语：

mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]; // N(D,S-1) + N(D-1,S-1)
if (j - f - 1 >= 0)                            // prevent index underrun
    mem[i][j] -= mem[i - 1][j - f - 1];        // - N(D-1,S-F-1)

此外，如果您设置

N(0,0) = 1，N(0，S) =0

换言之：

mem[0][0] = 1;  // all other mem[i][j] are 0 by default, right?

您可以将递归的基础向上移动一行，避免将D=1视为特例。

这就是代码的作用。让我们看一个例子。下面是F=3、D=2、S=8的计算表：

-------------------
|1|0|0|0|0|0|0|0|0|
-------------------
|0|1|1|1|0|0|0|0|0|
-------------------
|0|0|1|2|3|2|1|0|0|
-------------------

请注意，底部行的每个单元格中的值是上一行中左边的水平三个单元格条中值的总和，但也等于左边的值加上左上角的值减去左边的3个单元格的值。

Update:为了理解递归为什么工作，让我们看一下您提到的示例。有多少种方式来滚动4与2个正常的6面骰子？嗯，在这个简单的例子中，我们可以把所有可能的卷轴写在这样的表格里：

----------------------
|  | 1| 2| 3| 4| 5| 6|
----------------------
| 1| 2| 3| 4| 5| 6| 7|
----------------------
| 2| 3| 4| 5| 6| 7| 8|
----------------------
| 3| 4| 5| 6| 7| 8| 9|
----------------------
| 4| 5| 6| 7| 8| 9|10|
----------------------
| 5| 6| 7| 8| 9|10|11|
----------------------
| 6| 7| 8| 9|10|11|12|
----------------------

上一行和最左边列中的骰子上的值，以及其他单元格中的和值。我们可以立即看到，我们有三个组合的轧辊，加起来等于4，即(1,3)，(2,2)和(3,1)。到目前为止是微不足道的。

现在看看第二个骰子:在六面中，只有1，2，3的之和是4。我们可以用第二次骰子抛出1的方法是1，因为它只有一个边，它的数值是1。所以这并不会将任何乘法加到解中:每一个在第2模上有4和1和1的解也有3在第1模上。我们可以将第二次模具上有4和1和的每一个组合映射到第一个第一个骰子的抛出。所以，在第二个模具上可以有4和1和的方法的数目与在第一个模具上有4-1=3的方式相同。

在一般情况下也是如此。只要每一个数j只出现在Dth芯片上一次，就只有一种方法可以抛出它，那么在最后一个骰子上有这个数的每一个解都有一个1:1的映射，最后一个模上有这个数的和S到一个较小的D-1骰子和S-j之和的一个解决方案。因此，这种解决办法的数目必须相同。为j的所有可能值添加这一项，您就会到达递归步骤。

更新2

动态规划技术，利用原问题中的算法，解决“有多少种方式来滚动4与2个正常的6面骰子”产生的表格，如下图所示，该表已被注释，以帮助理解。这显示了在计算当前行的值时如何使用上一行的值：

通过对2个骰子的简单演练，可以将使用上一行值的相同逻辑应用于任意数量的骰子/任意目标和的其他问题。

更新3

上述演练的警告显示在下面的图像中，这是我们试图用两个骰子生成8个骰子的地方，每个骰子都有三个面；上面显示了用于这个步骤的表，但为了清晰起见，在这里重复。

在这种情况下，用更新2中描述的方式对上一行的值进行求和显然是不正确的，因为这意味着在骰子上使用由于面数限制而不存在的值。这是我们需要聪明的地方，我们使用什么值，这是在if的情况下，在张贴的算法，标记为混淆点B。