如何为Leetcode 1423可以从卡中获得的最大积分优化蛮力递归方法

Question

我在Leetcode上遇到了这个问题。问题描述如下

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.

Return the maximum score you can obtain.

Sample testcases
cardPoints = [1,2,3,4,5,6,1], k = 3 => Output is 12
cardPoints = [2,2,2], k = 2 => Output is 4
cardPoints = [9,7,7,9,7,7,9], k = 7 => Output is 55
cardPoints = [1,1000,1], k = 1 => Output is 1

查看讨论论坛后，我意识到可以将其转换为滑动窗口问题，我们必须找到smallest subarray sum of length len(cardPoints) - k。虽然我确实了解这一点，我尝试的最初方法是蛮力递归，并使用动态编程（内存化）来缓存中间结果。尽管如此，它仍然会导致超时。使用这种方法，我还有其他优化方法可以使我的代码运行得更快吗？

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

使用DP之前=>通过了16/40个测试用例，后跟TLE

使用DP之后=>通过了31/40个测试用例，后跟TLE

任何帮助将不胜感激。谢谢！

Answer 1

如果仔细看，可以通过滑动窗口来解决。如果我们忘记了领取的顺序，那么在第K个领取完成后有哪些可能的选择情况？

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

因此您可以计算前缀总和，并在O（1）时间内找出所有上述K + 1组合。为此，总时间复杂度为O（k），而O（n）中的前缀和计算。由于N> = k，所以时间复杂度O（n）