3

问题：有一个m x n网格（0 <= m, n <= 500）。网格中的每个单元格包含 k个硬币（k 也可以是负数或 0）。你从0, 0开始，到m-1, n-1结束，你可以向下移动 1 步或向右移动 1 步，收集尽可能多的硬币。如果k < 0，则该特定单元格有强盗，您无法进入该单元格。如果您进入8个相邻单元中的任何一个，您将被抢走k个硬币。当你到达m-1, n-1时你会有多少硬币？

例如在网格中：

0,23,20,-32
13,14,44,-44
23,19,41,9
46,27,20,0

ans = 129（按照路径：0-13-23-46-27-20-0）

时间限制：5秒

我不认为这个程序可以使用动态编程来解决。而且我还没有研究过图论（以防它可以用来解决这个问题）。直接递归的方法是我唯一能想到的，在给定的约束下效率太低了。

那么解决这个问题的好方法是什么？不要只是发布代码，告诉我如何开始。如果它与图论有关，那么指出涉及哪个定理将非常有用。

4

3 回答 3

4

您的问题称为加权有向无环图的最长路径问题。

当您到达 (x,y) 时，您可以拥有的最多硬币数量由下式给出：

coins(x,y) = max(coins(x-1,y), coins(x,y-1)) + change

这是一种重复关系。它可以通过使用递归和记忆来解决，也可以通过使用迭代算法来解决。

迭代算法是一次通过一个对角线的网格。从 0,0 开始。然后计算 0,1 和 1,0。然后是 0,2 和 1,1 和 2,0。ETC...

步骤1：

 0,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?

第2步：

 0, 23,  ?,  ?
13,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?

第 3 步：

 0, 23,-33,  ?
13, 37,  ?,  ?   // 37 because of max(23,13) + 14
36,  ?,  ?,  ?
 ?,  ?,  ?,  ?

ETC...

完成此过程后，答案是右下角的数字。

于 2012-08-26T00:08:12.487 回答
4

我不认为这个程序可以使用动态编程来解决。

为什么不？这是动态规划方法的主要候选者。

直接递归的方法是我唯一能想到的，在给定的约束下效率太低了。

你能构建一个递归解决方案来解决，比如说，一个 5x5 网格吗？完美的！从它开始，然后通过为您已经解决的单元格添加一组最佳结果来记忆它。MxN以所有大的负值开始该数组，然后在找到更好的解决方案时对其进行更新。比已经存在的。完成单元格后，将解决方案放入MxN数组中：下次递归时，检查数组中的数字，如果存在值，则返回它而不继续递归。

记忆的解决方案本身相当简单。算法的预处理步骤（从相邻单元格中减去负数）需要更多代码。

int solve(int r, int c) {
    if(memo[r][c] != MIN) {
        return memo[r][c];
    }
    int res = grid[r][c];
    int a = 0, b = 0;
    if (r+1 != R) {
        a = solve(r+1, c);
    }
    if (c+1 != C) {
        b = solve(r, c+1);
    }
    res = max(res+a, res+b);
    return memo[r][c] = res;
}

这是ideone上的解决方案，它129按预期返回。

于 2012-08-26T00:11:09.830 回答
0

您的问题可以描述为最大流量问题，因此可以通过Ford-Fulkerson-Algorithm解决。

转换过程如下：

  • 删除负节点并从相邻单元格中减去它们的数量。
  • 0/0 将是源，m-1，n-1 是汇
  • 每个节点都连接到下方和右侧的节点，弧的容量等于其目标节点的值。
  • 现在最大流量等于你可以拥有的最大硬币数量

可能有更简单的解决方案，这只是我想到的第一件事。

编辑：正如 dasblinkenlight 在评论中指出的那样，这是行不通的，因为流程实际上是多条路径的组合，这当然不是我们想要的。

于 2012-08-26T00:10:09.520 回答