python - 通过二维数组查找路径，其总和最接近给定数字

Question

我想找到通过二维整数数组(无负数，大小 N*N)的路径，其中所有传递数字的总和最接近给定数字。从左上角开始，在浏览数组的每一步中，您只能向下或向右移动。目标是数组的右下角。

例子:

field = [
  [0,5,1],
  [1,3,5]
  [2,1,1]
]

n = 5

solution(field, n) => 0
// down, down, right, right

solution(field, 7) => 1

如果没有找到解决方案，则返回一个正数，返回 -1。

我低效的解决方案:

def solution(n, field)
  res​ ​=​ ​closest(n,​ ​field)
  if​ ​res​ ​<​ ​0:
    return​ ​-1
  ​return​ ​res

def closest(n, field)
  best = n - field[0][0]
  if len(field) > 1:
    "Remove upper most row and call recursively"
    tmp = solution(n - field[0][0], field[1:])
    if tmp >= 0:
  ​    best = tmp
  if len(field[0]) > 1:
    "Remove left most column and call recursively"
    tmp = solution(n - field[0][0], [(x[0:0] + x[1:]) for x in field])
    if tmp < best:
      best = tmp
  return best

这适用于小范围，但效率非常低。对于 20 列和 20 行的字段，找到解决方案需要很长时间。

有没有更有效的方法来解决这个问题。 (即 20*20 几秒钟)(代码不必在 python 中

Answer 1

您可以使用动态规划或记忆化来有效地解决这个问题。首先，递归函数是这样表述的:

C(x, y, n) =   -1 if x < 0 or y < 0 or x >= n or y >= n or n < 0 (1)
             | field[x][y] if x = n - 1 and y = n - 1 and n >= 0 (2)
             | -1 if FromUp = -1 and FromLeft = -1 (3)
             | field[x][y] + Max(FromUp, FromLeft) (4)
where C(x, y, n) is the length of the path closest to n ending at x and y
      FromLeft = C(x - 1, y, n - field[x][y])
      FromUp = C(x, y - 1, n - field[x][y])

有 2 种基本情况 (1) 和 (2)，(1) 表示无效的行或列或 n。 (2) 表示您已经到达右下角的有效 n 单元格。对于特定的 x、y 和 n，您可以来自上方的单元格或左侧的单元格。因此，(3) 是失败的递归情况，如果递归情况 1 成功，则 (4) 计算 C(x, y, n) 的正确长度。

如果你想使用动态规划，你可以构建一个 3D 表并用 3 个嵌套的 for 循环填充它。如果你想使用内存，只需编写上面的递归函数；但每次你返回一些东西时，将它记录在一个 3D 表中，并尝试在其他步骤之前首先在函数中使用表中的结果