Re: [閒聊] 每日leetcode
1937. Maximum Number of Points with Cost
## 思路
直接照題目暴力作DP的話 會TLE -- O(MN^2)
dp[r][c] = matrix[r][c] + max(dp[r-1][ci] - abs(c-ci))
拆解 max(dp[r-1][ci] - abs(c-ci))
分兩次for loop 由左往右/由右往左記錄curr_max
curr_max = max(curr_max-1, dp[r-1][c])
dp[r][c] = matrix[r][c] + curr_max
## Code
```python
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
len_r, len_c = len(points), len(points[0])
dp = [0] * len_c
for r in range(len_r):
next_dp = [0] * len_c
curr_max = 0
for c in range(len_c):
curr_max = max(curr_max - 1, dp[c])
next_dp[c] = points[r][c] + curr_max
curr_max = 0
for c in range(len_c-1, -1, -1):
curr_max = max(curr_max - 1, dp[c])
next_dp[c] = max(next_dp[c], points[r][c] + curr_max)
dp = next_dp
return max(dp)
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.178 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723871185.A.F9F.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 727 之 1548 篇)：