1937. Maximum Number of Points with Cost

approach 1: O(m * n * n) time complexity not acceptable

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0:
                    dp[0][j] = points[0][j]
                else:
                    for k in range(n):
                        dp[i][j] = max(dp[i][j], points[i][j] + dp[i-1][k] - abs(j-k))
        
        return max(dp[m-1])

dp[i][j] = max(dp[i][j], points[i][j] + dp[i-1][k] - abs(j-k))

dp[i][j] = max(dp[i][j], points[i][j]-j + dp[i-1][k]+k) if 0 <= k <= j
dp[i][j] = max(dp[i][j], points[i][j]+j + dp[i-1][k]-k) if j <= k <= n-1

so the problem is converted to find max dp[i-1][k]+k for 0 <= k <= j and max dp[i-1][k]-k for j <= k <= n-1. The max values are then stored in left[j] and right[j]

time complexity O(m * n)

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), 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):
            left, right = [0] * n, [0] * n
            
            left[0] = dp[i-1][0]
            for k in range(1, n): # 0 <= k <= j
                left[k] = max(left[k-1], dp[i-1][k] + k)
            
            right[n-1] = dp[i-1][-1] - n + 1
            for k in range(n-2, -1, -1): # j <= k <= n-1
                right[k] = max(right[k+1], dp[i-1][k] - k)
                
            for j in range(n):
                dp[i][j] = max(left[j] - j, right[j] + j) + points[i][j]
        
        return max(dp[m-1])

1937. Maximum Number of Points with Cost - cocoder39/coco39_LC GitHub Wiki