金矿问题--for循环序列

Question

金矿问题. 下面的for循环序列给出了正确的结果。

//see link for other code
static int getMaxGold(int gold[][], int m, int n) {
//see link for other code

       for (int col = n-1; col >= 0; col--) {
            for (int row = 0; row < m; row++) {
                int right = (col == n-1) ? 0 : goldTable[row][col+1];
                int right_up = (row == 0 || col == n-1) ? 0 : goldTable[row-1][col+1];
                int right_down = (row == m-1 || col == n-1) ? 0 : goldTable[row+1][col+1];
                goldTable[row][col] = gold[row][col] + Math.max(right, Math.max(right_up, right_down));
            }
        }
}
//see link for other code

而其他方式则没有得到预期的结果。例如

for (int col = 0; col < n; col ++) {
    for (int row = 0; row < m; row++) {
    //same code to calculate right, rightUp and rightDown
    }
}

对这种行为有什么解释吗？

Answer 1

你不需要存储整个矩阵。

当你建立表格时，你只需要保留你处理的最后一层。

在你的递归中，有对角线的右边，或者右边，所以这一层是一列，因为要计算某个单元格的值，你需要知道三个值（在它的右边）。

你的结论是（正如Damien已经发现的那样），你从最右边的列开始计算，那么为了计算n-1列的每一个单元格的值，你只需要知道第n列（你很幸运地已经计算了）。

在下面的例子中。m_ij 指的是 i-第线。j第-列。(例如 m_01 == 2, m_10 = 5)

1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 3

最后一栏是 {4,8,3,3}要计算 m_02 你需要选择 4 和 8

3 - 4
  \
    8

m_02 = 3 + 8 = 11

要计算 m_12 你需要选择 4, 8 和 3

    4
  /
7 - 8
  \
    3

m_12 = 7 + 8 = 15

跳过的东西

m_22 = 2 + 8 = 10
m_32 = 6 + 3 = 9

现在你知道了第三列中每个方格的最大值

1 2 11 .
5 6 15 .
9 1 10 .
4 5 9  .

你也是这样做的 m_10, m_11...同上

m_01 = 2 + max(11, 15) = 17
m_11 = 6 + 15
m_21 = 1 + 15
m_31 = 5 + 10

因此，留给我们处理的是

1 17
5 21
9 16
4 15

然后

1+21
5+21
9+21
4+16

最后得分=max(22, 26, 30, 20)

正如你所注意到的，你 只是 需要跟踪最后处理的列。而不是一整张表的计算。而且最后处理的列必须从右边开始，而且必须是最右边的一列......

我不认为一个实现可以帮助你理解，但如果是

const s = `
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 3`

const m = s.trim().split('\n').map(x => x.trim().split(' ').map(y => parseInt(y)))
let layer = [0, 0, 0, 0]
for (let j = 3; j >= 0; --j) {
  const nextLayer = []
  for (let i = 0; i < 4; ++i) {
    nextLayer[i] = m[i][j] + Math.max(
      layer[i-1] || 0, // we default undefined value as 0 supposing s only holds positive coefficient
      layer[i],
      layer[i+1] || 0
    )
  }
  layer = nextLayer
}
console.log(Math.max(...layer))