We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Points with Cost

Number: 2067

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft

Problem Description

Given an m x n integer matrix points, pick one cell from each row so that your total score is maximized. If you select cell (r, c) in a row, you add points[r][c] to your score. However, for every two consecutive rows, you subtract the absolute difference of their column indices from your score (i.e. if you picked c1 in row r and c2 in row r+1, you subtract abs(c1 - c2)). The goal is to determine the maximum possible score.

Key Insights

  • Use dynamic programming to store the best achievable score ending at each column.
  • Transition between rows must incorporate the cost of changing columns, given by abs(c1 - c2).
  • Precompute two helper arrays (left and right) for each row to capture the maximum score obtainable from left-to-right and right-to-left, effectively handling the absolute difference cost in O(n) time per row.
  • This optimized transition allows for solving the problem efficiently without using a nested loop for cost computation.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(n), since only one-dimensional arrays (dp, left, right) are maintained for computations.

Solution

The solution involves dynamic programming by tracking the maximum score achievable at each cell of the current row. For each row beyond the first, two helper arrays, left and right, are computed:

  • The left array is built by iterating from left to right, adjusting the score by subtracting 1 for each move to the right.
  • The right array is built by iterating from right to left, similarly subtracting 1 for each move to the left. Then, for every cell in the new row, the best possible previous score is added from either the left or right helper array along with the current cell's points. This trick avoids the need for an inner loop to compute the absolute difference cost for every pair of columns, thereby optimizing the transition.

Code Solutions

# Function to calculate the maximum number of points
def maxPoints(points):
    m = len(points)
    n = len(points[0])
    # dp will track the maximum score ending in each column for the previous row
    dp = points[0][:]  # Copy the first row as initial state

    # Process each row from the second row onward
    for i in range(1, m):
        # Create helper arrays to capture best previous scores adjusting for movement costs
        left = [0] * n
        right = [0] * n

        # Build the left helper array from left to right
        left[0] = dp[0]
        for j in range(1, n):
            left[j] = max(left[j - 1] - 1, dp[j])
        
        # Build the right helper array from right to left
        right[n - 1] = dp[n - 1]
        for j in range(n - 2, -1, -1):
            right[j] = max(right[j + 1] - 1, dp[j])
        
        # Update dp for the current row using the best scores from left and right arrays
        new_dp = [0] * n
        for j in range(n):
            new_dp[j] = points[i][j] + max(left[j], right[j])
        dp = new_dp  # Move to the next row

    # The answer is the maximum value in the final dp row
    return max(dp)

# Example usage:
if __name__ == '__main__':
    points_example = [[1,2,3],[1,5,1],[3,1,1]]
    print(maxPoints(points_example))  # Expected output: 9
← Back to All Questions