algorithm - 允许特殊 Action 的格网游戏-ZCO 2009，P1

您会得到一个正数和负数的正方形网格。您必须从网格的左上角开始，并找到到右下角的路径。在每个步骤中，只允许您将一个位置向右移动或向下移动一个位置。作为一项特殊的奖励，最多允许您向左或向上移动一次。请注意，由于此特殊举动，您可以多次访问某个职位。
您的目标是找到具有最大权重的路径，其中路径的权重是沿路径访问的所有数字的总和。

大家好!上面的问题是我无法解决的问题:(
Link to full Problem Here
我认为，现在这个问题的主要困难在于可以采取的特殊奖励措施。我在如何决定必须在何处进行奖金转移以及如何继续充分利用该收益方面遇到困难。我认为贪婪算法不会在这里起作用，因为我们还必须照顾将来的步骤，而不仅仅是局部最优的步骤。我首先想到的是一种算法，该算法将使用贪婪方法来移动并达到最大值，但再次似乎无效。
有人可以建议我一些方法来解决这个问题，还有更多类似的问题吗？任何帮助，将不胜感激。谢谢!

最佳答案

让f(i, j, w)代表直到单元格(i, j)的最佳解决方案，其中w具有以下三种状态之一:before，after和right_after是一种特殊的动作。然后通常:

f(i, j, before) = M(i, j) + max(
  f(i-1, j, before),
  f(i, j-1, before)
)

f(i, j, after) = M(i, j) + max(
  f(i-1, j, after),
  f(i, j-1, after),
  f(i-1, j, right_after),
  f(i, j-1, right_after)
)

f(i, j, right_after) = M(i, j) + max(
  f(i+1, j, before),
  f(i, j+1, before)
)

JavaScript代码(未记录，自下而上，留给读者):

function f(M, i, j, w){
  if (i == 0 && j == 0 && w != 'right_after')
    return M[i][j]

  if (i < 0 || i > M.length-1 ||
    j < 0 || j > M[0].length-1)
    return -Infinity

  if (w == 'before'){
    return M[i][j] + Math.max(
      f(M, i-1, j, 'before'),
      f(M, i, j-1, 'before'))
  }

  if (w == 'after'){
    return M[i][j] + Math.max(
      f(M, i-1, j, 'after'),
      f(M, i, j-1, 'after'),
      f(M, i-1, j, 'right_after'),
      f(M, i, j-1, 'right_after'))
  }

  if (w == 'right_after'){
    return M[i][j] + Math.max(
      f(M, i+1, j, 'before'),
      f(M, i, j+1, 'before'))
  }
}

var M = [
  [12, -16, 10, -12],
  [-16, 13, -14, 7],
  [7, -4, 16, -15],
  [-7, 16, -9, 8]
]

var m = M.length
var n = M[0].length

console.log(Math.max(
  f(M, m-1, n-1, 'before'),
  f(M, m-1, n-1, 'after')
))

关于algorithm - 允许特殊 Action 的格网游戏-ZCO 2009，P1，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59101456/