在Python中查找从消失的coin矩阵中可以获得的最大硬币数量的程序

在Python中查找从消失的coin矩阵中可以获得的最大硬币数量的程序

假设我们有一个2D矩阵,其中每个单元matrix[r,c]代表该单元格中存在的硬币数量。当我们从matrix[r,c]中取出硬币时,行(r-1)和(r+1)上的所有硬币将消失,并且matrix[r,c + 1]和matrix[r,c-1]处的硬币也会消失。我们必须找到我们可以收集的最大硬币数量。

所以,如果输入是:

2 8 7 6
10 10 4 2
5 9 2 3

那么输出将是26,因为我们可以选择带有硬币8、6、9和3的单元格,总共是26。

为了解决这个问题,我们将遵循以下步骤:

  • 定义一个函数getmax(),它将获取arr
  • prev_max:=0
  • curr_max:=0
  • res:=0
  • 对于arr中的每个数字,执行以下操作:
    • temp:=curr_max
    • curr_max:=num+prev_max
    • prev_max:=temp和prev_max的最大值
    • res:=res和curr_max的最大值
  • 返回res
  • 从主方法执行以下操作:
    • 如果matrix为空,则
      • 返回0
    • m:=matrix的行数
    • n:=matrix的列数
    • row_sum:=大小为m的数组,并以0填充
    • 对于0到m-1的范围内的i,执行以下操作:
      • row_sum[i]:=getmax(matrix[i])
    • 返回getmax(row_sum)

示例

让我们看一下以下实现,以便更好地理解-

def getmax(arr):
   prev_max, curr_max = 0, 0
   res = 0
   for num in arr:
      temp = curr_max
      curr_max = num + prev_max
      prev_max = max(temp, prev_max)
      res = max(res, curr_max)
   return res

def solve(matrix):
   if not matrix:
      return 0
   m, n = len(matrix), len(matrix[0])
   row_sum = [0 for _ in range(m)]
   for i in range(m):
      row_sum[i] = getmax(matrix[i])
   return getmax(row_sum)

matrix = [
   [2, 8, 7, 6],
   [10, 10, 4, 2],
   [5, 9, 2, 3]
]
print(solve(matrix))

输入

[
[2, 8, 7, 6],
[10, 10, 4, 2],
[5, 9, 2, 3
]

输出

26

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程