Leetcode 2067 Solution

This article provides solution to leetcode question 2067 (maximum-number-of-points-with-cost)
Categories:
Tags:
Access this page by simply typing in "lcs 2067" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/maximum-number-of-points-with-cost

Solution

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m = len(points)
        n = len(points[0])

        dp = [[0 for _ in range(n)] for _ in range(m)]
        for j in range(n):
            dp[0][j] = points[0][j]

        for i in range(1, m):
            opt = 0
            for j in range(n):
                opt = max(opt, dp[i - 1][j])
                dp[i][j] = max(dp[i][j], points[i][j] + opt)
                opt -= 1

            opt = 0
            for j in range(n - 1, -1, -1):
                opt = max(opt, dp[i - 1][j])
                dp[i][j] = max(dp[i][j], points[i][j] + opt)
                opt -= 1

        print(dp)

        return max(dp[-1])