1937. Maximum Number of Points with Cost

[zeikar]

Problem link

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

Problem Summary

2차원에서 점수를 먹는 문제. 먹을 때 이전에 먹은 열과 비교해서 그 차이만큼은 빼야 한다.

Solution

3차원 dp는 쉽다. 다만 시간 초과.
2차원으로 어떻게 하면 줄일 수 있을까?

왼쪽에서 왔을 때의 최대와 오른쪽에서 왔을 때의 최대를 같이 구해서 그 중 최대값으로 업데이트하면 된다.

에디토리얼 참고.

간단하게 설명하면 left_max[i]는 i보다 왼쪽의 점수 중에 최대, right_max[i]는 i보다 오른쪽의 점수 중에 최대로 하고 거리에 따라 점수를 보정한다고 생각하면 된다.

이렇게 하면 시간복잡도는 O(m*n)

Source Code

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m = len(points)
        n = len(points[0])
        dp = [[0] * n for _ in range(m)]

        for i in range(n):
            dp[0][i] = points[0][i]

        for i in range(1, m):
            leftMax = [0] * n
            leftMax[0] = dp[i - 1][0]
            for j in range(1, n):
                leftMax[j] = max(leftMax[j - 1] - 1, dp[i - 1][j])

            rightMax = [0] * n
            rightMax[-1] = dp[i - 1][-1]
            for j in range(n - 2, -1, -1):
                rightMax[j] = max(rightMax[j + 1] - 1, dp[i - 1][j])

            for j in range(n):
                dp[i][j] = points[i][j] + max(leftMax[j], rightMax[j])

        return max(dp[-1])