我最近遇到了一个问题。我必须找到从一个多维整数数组的左上角到右下角的路径的代价。这条路径的成本必须是不超过特定提供价值的最大成本。
路径的成本定义为该路径所经过的数组索引值的总和。每条路径的起点始终在左上角，每条路径的终点始终在右下角。此外，您只能向右或向底部移动。
假设这是我要用于这个问题的多维数组，提供的值是12。
+---+---+---+
| 0 | 2 | 5 |
+---+---+---+
| 1 | 1 | 3 |
+---+---+---+
| 2 | 1 | 1 |
+---+---+---+
这是我应该找到的正确路径。该路径的成本为11，它是低于或等于给定值的任何路径中的最高成本。
+---+---+---+
| X | X | X |
+---+---+---+
| 1 | 1 | X |
+---+---+---+
| 2 | 1 | X |
+---+---+---+
我曾试图用Python解决这个问题，但我看不出哪里出了问题。下面是我的代码片段。
def answer (food, grid):
# Grid is N*N in size
n = len(grid)
# Memoize a given function
def memoize (f):
memo = {}
def helper (r, c, k):
i = c + (r * n)
if i not in memo:
memo[i] = f(r, c, k)
return memo[i]
return helper
# Get cost function
def get_cost (r, c, k):
if r >= n or c >= n:
return -1
if k < grid[r][c]:
return -1
if r == n - 1 and c == n - 1:
return grid[r][c]
down = get_cost(r + 1, c, k - grid[r][c])
right = get_cost(r, c + 1, k - grid[r][c])
if down < 0 and right < 0:
return -1
return grid[r][c] + max(down, right)
# Memoize the get cost function
get_cost = memoize(get_cost)
return get_cost(0, 0, food)
print answer (12, [[0, 2, 5], [1, 1, 3], [2, 1, 1]])
我总是得到16的答案，而我应该得到11的答案。有人能帮我吗？
编辑：
我更改了我的记忆代码，将给定的食物价值包含在索引中。我得到了正确的答案。然而，仍有其他情况不起作用。（在这些情况下，我没有得到输入，所以我看不出哪里出了问题）。
这是我更新的代码。
# Memoize a given function
def memoize (f):
memo = {}
def helper (r, c, k):
i = (k * food) + (c + (r * n))
if i not in memo:
memo[i] = f(r, c, k)
return memo[i]
return helper
您可以将memoize函数更新为以下内容：
def memoize (f):
memo = {}
def helper(*args):
if args not in memo:
memo[args] = f(*args)
return memo[args]
return helper
grid = [[0,2,5],[1,1,3],[2,1,1]]
answer(12, grid)
# 11
只要参数是可散列的，就可以将*args用作函数的参数，将args用作内存缓存的键。这和使用参数的元组作为键是一样的。
def fn(*args):
print(args)
fn(1,2,3)
(1, 2, 3)
考虑到k，由i = c + (r * n)组成的原始存储高速缓存密钥被排除在外，并且还允许不同c和r组合的可能冲突。
我想分享一种使用回溯的不同方法：
def find_path(food, grid):
n = len(grid)
def worker(cost, path):
row, col = path[-1]
if row == n - 1 and col == n - 1:
# we reached the bottom right corner, exit now
return cost, path
possible_paths = []
if row < n - 1:
# we can go down
cost_down = cost + grid[row+1][col]
path_down = list(path)
path_down.append((row+1, col))
possible_paths.append(worker(cost_down, path_down))
if col < n - 1:
# we can go to the right
cost_right = cost + grid[row][col+1]
path_right = list(path)
path_right.append((row, col+1))
possible_paths.append(worker(cost_right, path_right))
# a path is valid, if its cost is
# less or equal to the food available
valid_paths = [item for item in possible_paths
if item is not None
and item[0] <= food]
if valid_paths:
return max(valid_paths, key=lambda x: x[0])
return None
return worker(grid[0][0], [(0, 0)])
该算法递归地遍历数组，并不断寻找所有可能的路径。如果路径成本高于限制（food），则丢弃该路径成本；否则，所有可能的下一步都在尝试中。当到达右下角时，辅助函数终止，并比较不同的路径。
这样也可以检测到没有任何可能路径的阵列：
print(find_path(12, [[0, 2, 5],
[1, 1, 3],
[2, 1, 1]]))
# (11, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)])
print(find_path(12, [[0, 2, 5],
[1, 1, 3],
[2, 1, 10]]))
# None
print(find_path(42, [[3, 8, 6, 5],
[1, 5, 3, 9],
[1, 5, 8, 1],
[2, 1, 9, 4]]))
# (42, [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (3, 2), (3, 3)])