数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：找出可从左上角拾取到右下角单元格的硬币数量
假设我们有一个二维矩阵，其中有3个可能的值：
0 代表空单元格。
1 代表一枚硬币。
-1 代表一堵墙。
我们必须找到从左上角单元格开始，只能向右或向下移动到达右下角单元格，然后只能向上或向左移动返回左上角单元格，可以拾取的最大硬币数量。如果无法到达右下角单元格，则返回0。拾取硬币后，单元格值变为0。
例如，如果输入如下：
| 0 | 1 | 1 |
| 1 | 1 | 1 |
| -1 | 1 | 1 |
| 0 | 1 | 1 |
则输出为8。
为了解决这个问题，我们将遵循以下步骤：
n := mat的行数，m := mat的列数
定义一个函数 util()。它将接收 i, j, k, l 作为参数。
如果 i 和 j 超出 mat 的范围，或者 mat[i, j] 等于 -1，则
返回 -inf（负无穷大）
如果 k 和 l 超出 mat 的范围，或者 mat[k, l] 等于 -1，则
返回 -inf（负无穷大）
如果 i, j, k 和 l 全部为 0，则
返回 mat[0, 0]
best := -inf（负无穷大）
对于每个 (dx1, dy1) 对 in [(−1, 0) ,(0, −1) ]，执行：
对于每个 (dx2, dy2) 对 in [(−1, 0) ,(0, −1) ]，执行：
best := best 和 util(i + dy1, j + dx1, k + dy2, l + dx2) 的最大值
返回 mat[i, j] + (当 i 不等于 k 时为 1，否则为 0) * mat[k, l] + best
在主方法中执行以下操作：
返回 0 和 util(n − 1, m − 1, n − 1, m − 1) 的最大值
让我们看下面的实现来更好地理解：
示例
class Solution: def solve(self, mat): n, m = len(mat), len(mat[0]) def util(i, j, k, l): if not (0 <= i < n and 0 <= j < m) or mat[i][j] == −1: return −1e9 if not (0 <= k < n and 0 <= l < m) or mat[k][l] == −1: return −1e9 if i == 0 and j == 0 and k == 0 and l == 0: return mat[0][0] best = −1e9 for dx1, dy1 in [(−1, 0), (0, −1)]: for dx2, dy2 in [(−1, 0), (0, −1)]: best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2)) return mat[i][j] + (i != k) * mat[k][l] + best return max(0, util(n − 1, m − 1, n − 1, m − 1)) ob = Solution() matrix = [ [0, 1, 1], [1, 1, 1], [1, −1, 1], [0, 1, 1] ] print(ob.solve(matrix))
输入
[ [0, 1, 1], [1, 1, 1], [1, −1, 1], [0, 1, 1] ]
输出
8
更新于：2020-12-26
浏览量：104
广告