Leetcode 1423：如何优化暴力递归方法？

Question

我在 Leetcode 上遇到了 this question。问题描述如下

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

查看论坛后，我意识到这可以转换为滑动 window 问题，我们必须找到 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

如果仔细看，滑动window即可解决。第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)

Leetcode 1423：如何优化暴力递归方法？

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

c++

algorithm

memoization

dynamic-programming