计算二维数组中的最大路径和

Question

在准备编码面试时，我发现了这个问题，但正在努力解决它。我非常确定需要使用递归，但我似乎无法正确使用它。

二维数组表示城市地图，其中索引处的值表示该城市的宝藏数量。数组中有些值为零（表示不能交叉）

目标：给定一个二维数组，return一个整数，表示您从一个城市到另一个城市可以收集的最大宝藏数量。

规则：

可以从数组中的任意位置开始
避免零（即不能交叉）
您一次可以在 1 个索引处上下左右移动
不同途径可能获得相同数量的宝物
一张空地图应该return 0
如果映射包含正整数以外的任何值，函数应该return -1

例如。地图 1：
[[ 3, 0, 0, 1, 2],
[ 0, 1, 4, 0, 0],
[ 5, 0, 0, 3, 3]]

最高奖励为 6 件物品 (3,3)

我尝试过的：
我尝试创建两个 for 循环来访问每个索引：首先，我检查当前索引不为零或 -1。如果不是，那么我将当前索引处的值添加到一个空数组，其中每个路径指示不同的位置。 IE。左 = arr[0]，右 = arr[1]，等等。然后找到可能的路径并重复相同的过程直到我的数组索引值为零（对于所有路径）。

如果有人能在 python 中提供解决方案，将不胜感激。

Answer 1

下面是一个使用简单递归来解决这个问题的天真的方法。但是，如果有更智能的解决方案（最好是不使用递归），我不会感到惊讶。

import numpy as np

reward_map = np.array(
    [[ 3, 0, 0, 1, 2],
     [ 0, 1, 4, 0, 0],
     [ 5, 0, 0, 3, 3]])

print("Reward map:")
print(reward_map)

# This function checks if [i,j] are valid indices for the matrix "mat"
def are_valid_idcs(mat, i, j):
    return i >= 0 and j >= 0 and i < mat.shape[0] and j < mat.shape[1]

# This is the recursive function that computes the value given a starting point
def get_cell_value(reward_map, i, j):
    if ( not are_valid_idcs(reward_map, i, j) ) or reward_map[i,j] == 0.:
        return 0.
    else:
        # If we are in a "city", we want to check the connected squares. 
        # However, from there, we do not want to walk back.
        # That's why I copy the whole map and set [i,j] = 0, meaning this coordinate has already been handled.
        # This is important. If we do not do this, the recursion will not stop.
        submap = np.array(reward_map)
        submap[i,j] = 0.
        
        # Now we compute the value of our neighbors
        value_left = get_cell_value(submap, i-1, j)
        value_right = get_cell_value(submap, i+1, j)
        value_top = get_cell_value(submap, i, j-1)
        value_bottom = get_cell_value(submap, i, j+1)
        
        # And add everything together
        return value_left + value_right + value_top + value_bottom + reward_map[i,j]


# Here, we will remember the value and the coordinates where we started
values_per_idcs = []

# Loop over all cells and compute which value we can get if we start at that point
for i in range(reward_map.shape[0]):
    for j in range(reward_map.shape[1]):
        values_per_idcs += [ [ get_cell_value(reward_map, i, j), i, j] ]

# Now we build a numpy [n,3]-array over the results, where n is the total amount of elements in the map
# The 3 components in the 1-axis correspond to [value, i, j].
values_per_idcs = np.array(values_per_idcs, dtype=np.int64)

# Check if there are negative values in the map
if np.any(reward_map < 0):
    print(f" Value is -1 (due to negative values in reward map)")
# Check if all values are integer
elif not issubclass(reward_map.dtype.type, np.integer):
    print(f" Value is -1 (due to non-integer values in reward map)")
# If the input is OK, we can output the actual results
else:
    # in the [n,3]-result-array, find the n which has the maximum value (i.e. at position 0 on axis 1)
    best = np.argmax( values_per_idcs[...,0], axis=0 )
    
    # Print the best coordinate
    print(f"Maximum value is {values_per_idcs[best,0]} at indices {values_per_idcs[best,1], values_per_idcs[best,2]}")
    
    # Plot the suggested starting point which is easier for humans to read than the coordinates
    print("Suggested start-point:")
    starter = np.zeros_like(reward_map, dtype=np.int8)
    starter[values_per_idcs[best,1], values_per_idcs[best,2]] = 1
    print(starter)

输出：

Reward map:
[[3 0 0 1 2]
 [0 1 4 0 0]
 [5 0 0 3 3]]
Maximum value is 6 at indices (2, 3)
Suggested start-point:
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 1 0]]

适合您的练习任务：

请注意，此方法是 sub-optimal，因为它会为集群中的每个城市重新计算该集群的值。因此，如果我们的 reward_map 是一个仅包含 1 的 [n,m] 矩阵，它将开始 所有 n*m 的完整递归 坐标，这很糟糕。对您来说，一个好的做法是通过更新递归内部的 reward_map 来解决此问题，这样 reward_map[i,j]=0. 对于递归中曾经处理过的每个 [i,j]。

如果您对此回答满意，请不要忘记采纳。

计算二维数组中的最大路径和

Calculate the Maximum Path Sum in a 2D array

python

arrays

recursion