找出可以在Python中收集的最大硬币数量的问题
假设我们有一个二维矩阵，其中的单元代表其中的硬币数量。我们有两个朋友来收集硬币，它们分别位于开始时的左上角和右上角。他们遵循以下规则：
硬币收集器可以从单元格(i,j)移至单元格（i+1，j-1），（i+1，j）或（i+1，j+1）。
到达牢房后，他们会收集所有可用硬币，使牢房变空。
收藏家可以选择留在一个牢房，但是任何一个牢房中的硬币只能收集一次。
我们必须找到可以收集的最大硬币数量。
所以，如果输入像
那么输出将为17。
为了解决这个问题，我们将遵循以下步骤-
A：=输入矩阵
R：=A的行数
C：=A的列数
定义一个功能dp()。这将需要r，c1，c2
对于[c2−1，c2，c2+1]中的每个nc2，执行
ans：=ans和（base+dp（r+1，nc1，nc2））的最大值
如果0<=nc1<C和0<=nc2<C，则
返回0
如果r与R相同，则
ans：=A[r，c1]+（如果c1不等于c2，则1否则为0）*A[r，c2]
基本：=ans
对于[c1−1，c1，c1+1]中的每个nc1，执行
返回ans
返回dp（0，0，C−1）
让我们看下面的实现以更好地理解-
示例
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
def dp(r, c1, c2):
if r == R:
return 0
ans = base = A[r][c1] + (c1 != c2) * A[r][c2]
for nc1 in [c1 − 1, c1, c1 + 1]:
for nc2 in [c2 − 1, c2, c2 + 1]:
if 0 <= nc1 < C and 0 <= nc2 < C:
ans = max(ans, base + dp(r + 1, nc1, nc2))
return ans
return dp(0, 0, C − 1)
ob = Solution()
print(ob.solve([
[0, 4, 1, 0],
[3, 1, 4, 0],
[2, 5, 1, 1],
[3, 0, 0, 0]
]))输入值
[ [0, 4, 1, 0], [3, 1, 4, 0], [2, 5, 1, 1], [3, 0, 0, 0] ]输出结果
17