利特码1423：如何优化蛮力递归方法？

Question

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

一行有几张卡片，每张卡片都有一个相关的点数，点数用整数组cardPoints给出。

在一个步骤中，你可以从行的开始或结束处抽取一张牌。你必须准确地抽取k张牌。

你的分数是你所拿的牌的分数的总和。

给定整数组cardPoints和整数k，返回你能得到的最大分数。

例子1.输入：cardPoints = [1]:

输入: cardPoints = [1,2,3,4,5,6,1], k = 3 输出: 12 解释。 在第一步之后，你的分数永远是1，但是，先选择最右边的牌会使你的总分数最大化。最佳的策略是选择右边的三张牌，最后的得分是1+6+5=12。例子2.输入: cardPoints = [2]:

输入: cardPoints = [2,2,2], k = 2 输出: 4 解释: 无论你拿哪两张牌，你的分数都是4。例子3.输入: cardPoints = [9,2], k = 2, 输出: 4:

输入：卡点=[9,7,7,9,7,7,9]，k=7 输出：55 说明：无论你拿哪两张牌，你的分数都是4。55 解释: 你必须拿下所有的牌。你的分数是所有牌的分数之和。例4.你的分数是所有牌的分数之和。

输入: cardPoints = [1,1000,1], k = 1 输出: 1 说明：你不能拿中间的牌。你不能拿中间的牌。你的最好成绩是1。

输入: cardPoints = [1,79,80,1,1,1,1,200,1], k = 3 输出: 202

约束。

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

看了一下讨论区，我意识到这可以转化为一个推拉窗问题，我们要找到 smallest subarray sum of length len(cardPoints) - k. 虽然我明白这一点，但我最初尝试的方法是蛮力递归，并使用动态编程（memoization）来缓存中间结果。尽管这样，它的结果仍然是超时。我有没有其他的优化方法可以让我的代码使用这种方法运行得更快？

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 => 1640个测试用例通过后，TLE

在使用DP => 3140个测试用例通过后，TLE

任何帮助将被感激。谢谢！我在Leetcode上看到了这个问题。

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

所以你可以计算前缀和，并找出所有上述K+1组合在O(1)时间.总的时间复杂度将是O(k)这和前缀和计算在O(n)。由于N>=k所以，时间复杂度O(n)