最大总和的动态规划方法

Question

金矿问题

这是在面试问题中提出的，但我无法理解测试用例

就像在 ex 1->我知道最大 ans 会增加 6,4,2，但是 {（1,0）->（

2,1）->（2,2）} 这些移动如何采用这些值 6,4,2;和在 （1,0） 上，它将从上到下移动，这不是有效的移动

金矿问题

给定一个 n*m 维度的金矿。该矿中的每个字段都包含一个正整数，即以吨为单位的黄金量。最初，矿工位于第一列，但可以在任何行。他只能从给定的单元格移动（右>，右上/，右下），矿工可以向右或向右斜向上或向右斜向下移动到单元格。找出他可以收集的最大黄金数量。

    Input : mat[][] = {{1, 3, 3},
                       {2, 1, 4},
                      {0, 6, 4}};
    Output : 12 
    {(1,0)->(2,1)->(2,2)}
    Input: mat[][] = { {1, 3, 1, 5},
                       {2, 2, 4, 1},
                       {5, 0, 2, 3},
                       {0, 6, 1, 2}};
    Output : 16
    (2,0) -> (1,1) -> (1,2) -> (0,3) OR
    (2,0) -> (3,1) -> (2,2) -> (2,3)
    Input : mat[][] = {{10, 33, 13, 15},
                      {22, 21, 04, 1},
                      {5, 0, 2, 3},
                      {0, 6, 14, 2}};
    Output : 83

Answer 1

我相信

你误解了符号。

   C0 - C1 - C2 
R0 1    3    3
R1 2    1    4
R2 0    6    4

行用 R 标记，列用 C 标记。

Output : 12 
{(1,0)->(2,1)->(2,2)}

方法：

{（R1， C0） -> （R2，

C1） -> （R2， C2）}

• 由于您可以从第一列的任何行开始，因此从第 1 列开始。
• 然后向右向下移动
• 然后向右移动。

另一个示例使用相同的表示法。希望这有帮助！