Leetcode: 1937. Maximum Number of Points with Cost
2021/9/11 23:08:52
本文主要是介绍Leetcode: 1937. Maximum Number of Points with Cost,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Description
You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score. Return the maximum number of points you can achieve. abs(x) is defined as: x for x >= 0. -x for x < 0.
Example
Input: points = [[1,2,3],[1,5,1],[3,1,1]] Output: 9 Explanation: The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0). You add 3 + 5 + 3 = 11 to your score. However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score. Your final score is 11 - 2 = 9.
Tips
m == points.length n == points[r].length 1 <= m, n <= 105 1 <= m * n <= 105 0 <= points[r][c] <= 105
分析
如果不需要 abs(c1 -c2),那么这题将会比较简单。加上限制条件后,作一些转换可以将 abs 消除掉 #(r, c1) and (r + 1, c2) will subtract abs(c1 - c2) 1): dp[r+1][c2] = max( dp[r][c1] + c2 -c 1) // 保证 c2 >= c1 2): dp[r+1][c3] = max( dp[r][c1] + c1 -c3) // 保证 c1 >= c3 化简为 dp[r+1][c2] = c2 + max(dp[r][c1] - c1) // c2 >= c1 dp[r+1][c3] = -c3 + max(dp[r][c1] + c1). // c1 >=c3 class Solution(object): def maxPoints(self, points): """ :type points: List[List[int]] :rtype: int """ N = len(points) M = len(points[0]) memo = points[0] for i in range(1, N): tmp = [float('-inf')] * M m = float('-inf') for j in range(M): m = max(m, memo[j]+j) tmp[j] = -j + m + points[i][j] m = float('-inf') for j in range(M-1, -1, -1): m = max(m, memo[j]-j) tmp[j] = max(tmp[j], points[i][j]+m +j) memo = tmp return max(memo)
总结
速度上战胜了 80 % 的提交, 提交 3 次通过
这篇关于Leetcode: 1937. Maximum Number of Points with Cost的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享