Leetcode Daily Question 17/08/2024 - 1937. Maximum Number of Points with Cost

Problem 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.

#Advanced version
from typing import List
class Solution:
  def maxPoints(self, points: List[List[int]]) -> int:
    m = len(points)
    n = len(points[0])
    dp = [0] * n
    for i in range(m):
      new_dp = [0] * n
      for j in range(n):
        point = points[i][j]
        if i > 0:
          point += dp[j] 
        if j > 0:
          if point > new_dp[j-1] - 1:
            k = j
            while k >= 0 and new_dp[k] < point:
              new_dp[k] = point
              k -= 1
              point -= 1
          else:
            new_dp[j] = new_dp[j-1] - 1
        else:
          new_dp[j] = point
      dp = new_dp
    return max(dp)
  
# ------------------------------------------------------

#First version
from typing import List
class Solution:
  def maxPoints(self, points: List[List[int]]) -> int:
    m = len(points)
    n = len(points[0])
    dp = points[0][:]
    for i in range(1,m):
      left_dp = [0] * n
      right_dp = [0] * n
      left_dp[0] = dp[0]
      for j in range(1,n):
        left_dp[j] = max(left_dp[j-1] - 1, dp[j])
      right_dp[n-1] = dp[n-1]
      for j in range(n-2, -1, -1):
        right_dp[j] = max(right_dp[j+1] - 1, dp[j])
      
      for j in range(n):
        dp[j] = points[i][j] + max(left_dp[j], right_dp[j])
    return max(dp)

Explanation:

We can solve this problem by using dynamic programming to find the largest sum possible by considering all possible paths top down.

We shall present two solutions that utilises exactly the same idea. The difference is the first version is a clearer step by step approach, whereas the advanced version combines the steps in the first version into one pass.

The key idea of this problem is to traverse each row and keep track of two auxilary dp's, left_dp and right_dp.

The left_dp keeps track of the maximum points you can collect up to column j by considering paths that start from any column to the left of or including j in the previous row.

Similarly, the right_dp keeps track of the maximum points you can collect up to column j by considering that start from any column to the right of or including j in the previous row.

We can then update our total score attainable starting from each of the element in the top row.

Let's start by initiating our dp with the first row of points and traverse the row starting from the second row down.

def maxPoints(points):
  m = len(points)
  n = len(points[0])
  dp = points[0][:] #Initiate dp with first row of points
  for i in range(1,m):
    left_dp = [0] * n #max points attainable by traversing from the left
    right_dp = [0] * n #max points attainable by traversing from the right
    left_dp[0] = dp[0] #initiate left_dp by choosing our starting element
    for j in range(1,n):
      left_dp[j] = max(left_dp[j-1] - 1, dp[j]) #solving the subproblem
   	right_dp[n-1] = dp[n-1]
    for j in range(n-2,-1,-1):
      right_dp[j] = max(right_dp[j+1] - 1, dp[j])
    
    for j in range(n):
      dp[j] = points[i][j] + max(left_dp[j], right_dp[j]) #update dp by choosing the maximal path sum
      
  return max(dp)

Time Complexity:
left_dp: O(n)
right_dp: O(n)
dp: O(n)

Total: O(m*n)

Space Complexity:
left_dp: O(n)
right_dp: O(n)
dp: O(n)

Total: O(n)

We cannot make much improvements on time and space complexity. However, we can combine the two dp's, left_dp and right_dp into one operation to make the solution a single pass dp. This makes it practically faster by having to process less code.

For each row we initiate a new_dp array to keep track of the maximum score attainable up to points[i][j].

For each element in the row, we first add the value from the previous row's dp at the same column (dp[j]) to the current point value (points[i][j]).

Then, we compare this value with the value in the new_dp array for the previous column (new_dp[j-1] - 1). If the new value (point) is greater, you propagate this value to the left in new_dp, reducing the point and position as we move along.

if the current point is better than values in new_dp[j-1], we propagate this value leftward until it no longer improves the new_dp values.

def maxPoints(points):
  m = len(points)
  n = len(points[0])
  dp = [0] * n
  for i in range(m):
    new_dp = [0] * n
    for j in range(n):
      point = points[i][j]
      if i > 0:
        point += dp[j]
      if j > 0:
        if point > new_dp[j-1] - 1:
          k = j
          while k >= 0 and new_dp[k] < point:
            new_dp[k] = point
            point -= 1
            k -= 1
        else:
          new_dp[j] = new_dp[j-1] - 1
      else:
        new_dp[j] = point
      dp = new_dp
  return max(dp)

Both of the solutions can be found near the top of the page.