沿金字塔向下滑动时通过位移来决定向左或向右的方向

Question

我正在研究“金字塔向下滑动”问题 (https://www.mathblog.dk/project-euler-18/) 的解决方案，我需要帮助更直观地理解在内部循环中更新索引变量的解决方案背后的逻辑。

算法：

int posSolutions = (int)Math.Pow(2, inputTriangle.GetLength(0) - 1);
int largestSum = 0;
int tempSum, index;
 
for (int i = 0; i <= posSolutions; i++) {
    tempSum = inputTriangle[0, 0];
    index = 0;
    for (int j = 0; j < inputTriangle.GetLength(0) - 1; j++) {
        index = index + (i >> j & 1);
        tempSum += inputTriangle[j + 1, index];
    }
    if (tempSum > largestSum) {
        largestSum = tempSum;
    }
}

我一直在努力了解 index 变量是如何更新的以及它的用途。据我了解，使用 index 因此我们涵盖了金字塔中所有可能的路径（正如解决它的人所说“它用于决定是向右还是向左” ).但是我真的很难理解这个表达式中发生了什么：

index = index + (i >> j & 1);

所以，这是我所在的位置：

内部循环的循环次数与金字塔的楼层数一样多（-1 因为是顶层）。我们必须确保在每次迭代中，从我们的起点开始，我们必须覆盖所有可能的左右组合，一直到底层 - 这就是 index 的用途。但我不明白我怎么会想出那个表达。我已经尝试通过不同的金字塔楼层，记录不同的变量等，但我无法理解表达式。

非常感谢任何人的任何意见、建议或解释。谢谢！

Answer 1

算法的工作原理如下：

for (int i = 0; i <= posSolutions; i++) {

此循环旨在检查所有可能的解决方案。正在检查的解决方案由 i 表示。它本质上是一个位图，长度与三角形的深度相同。对于每一位，0 表示向左走，1 表示向右走，因此每个值唯一地表示从三角形的顶部到底部的路径。

index = 0;

index 变量表示要在 'current' 级别中查找的值。它从 0 开始，因为顶层只有 1 个值。然后它必须为每个后续级别增加 0（如果向左）或 1（如果向右）以确保您为当前解决方案添加正确的值 i。例如，如果您在一个级别中的位置 6，那么您需要移动到下一级中的位置 6 或位置 7，具体取决于相应位是否在 i.

中设置

for (int j = 0; j < inputTriangle.GetLength(0) - 1; j++) {

正如您所指出的，j 是金字塔的层级，从顶部开始。

    index = index + (i >> j & 1);

这是根据当前解决方案是要向左还是向右向索引添加 0 或 1 的表达式。 i >> j 将当前层 j 中 i 中的位移动到最右边的位置（即技术上最低有效位）。 & 1 然后清除除最右边的所有位，留下 0 或 1。然后将该值添加到索引以指向当前级别的正确值。

例如，如果正在查看的解决方案 (i) 是 12（或二进制 1100）并且我们正在考虑第三个级别，那么 index 将是 0 并且 j 将是 2。因此 i >> j 会将 i 右移 2 位以产生 11（二进制）。 & 1 将清除除最右边以外的所有位以产生 1。现在将其添加到 index 并且我们知道要查看第 2 行中的位置 1。

    tempSum += inputTriangle[j + 1, index];

这会将当前级别的值添加到总和中。

if (tempSum > largestSum) {
    largestSum = tempSum;
}

获得当前可能解决方案的总数后 i，将其与之前找到的最大总数进行比较。

最后几点：首先，您发布的代码中的变量命名不直观。更好的命名会使这个算法更容易理解。其次，有比您发布的蛮力算法更好的算法来解决这个问题。它们自下而上地工作，并且具有更易于理解的额外优势（在我看来）。

沿金字塔向下滑动时通过位移来决定向左或向右的方向

Bit-shifting to decide left or right direction when sliding down a pyramid

java

algorithm

bit-manipulation