Leetcode 1423: How to optimize brute-force recursive approach?

Question

I came across this question on Leetcode. The question description is as follows

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3 Output: 12 Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12. Example 2:

Input: cardPoints = [2,2,2], k = 2 Output: 4 Explanation: Regardless of which two cards you take, your score will always be 4. Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7 Output: 55 Explanation: You have to take all the cards. Your score is the sum of points of all cards. Example 4:

Input: cardPoints = [1,1000,1], k = 1 Output: 1 Explanation: You cannot take the card in the middle. Your best score is 1. Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3 Output: 202

Constraints:

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

After looking at the discussion forums, I realized that this could be converted into a sliding window problem where we have to find the smallest subarray sum of length len(cardPoints) - k. While I do understand this, The initial method I tried was brute-force recursive and used Dynamic Programming (memoization) to cache intermediate results. Despite this, it still results in a timeout. Is there any other optimization I can make to make my code run faster using this approach?

class Solution {
public:
    int maxScoreUtil(int left, int right,vector<int>& cardPoints, int k,vector<vector<int>>& dp){
        if(k == 0 || left == cardPoints.size() || right < 0)
            return 0;

        if(dp[left][right] != -1)
            return dp[left][right];

        int val_1 = maxScoreUtil(left+1,right,cardPoints,k-1,dp) + cardPoints[left];
        int val_2 = maxScoreUtil(left,right-1,cardPoints,k-1,dp) + cardPoints[right];

        return dp[left][right] = max(val_1,val_2);
    }

    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
        return maxScoreUtil(0,n-1,cardPoints,k,dp);
    }
};I

Before using DP => 16/40 test cases passed followed by TLE

After using DP => 31/40 test cases passed followed by TLE

Any help would be appreciated. Thanks!

Answer 1

if you closely look, it can be solved by sliding window. What are possible cases of selection after completion of Kth pick up if we forget the order we picked up?

The possible combinations will be:
0.  0 card picked up from rightmost, K cards picked up from leftmost
1.  1 card picked up from rightmost, K-1 cards picked up from leftmost
2.  2 cards picked up from rightmost, K-2 cards picked up from leftmost
3.  3 cards picked up from rightmost, K-3 cards picked up from leftmost
…………………………………………………………………………………….
k.   K cards picked up from rightmost, 0 card picked up from leftmost

so you can calculate prefix sum and find out all above K+1 combinations in O(1) time. total time complexity would be O(k) for this and prefix sum computing in O(n). Since N>=k so, time complexity O(n)