时间戳

首页 > 解决方案 > 为什么 DP 解决“您可以从卡中获得的最大积分”问题的速度太慢？

algorithm - 为什么 DP 解决“您可以从卡中获得的最大积分”问题的速度太慢？

问题描述

鉴于这个问题：

有几张牌排成一排，每张牌都有一个关联的点数，点数在整数数组 cardPoints 中给出。

在一个步骤中，您可以从行首或行尾取一张牌。你必须正好拿k张牌。

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

给定整数数组 cardPoints 和整数 k，返回您可以获得的最大分数。

示例 1：

输入：cardPoints = [1,2,3,4,5,6,1], k = 3

输出：12

说明：在第一步之后，您的分数将始终为 1。但是，首先选择最右边的卡将使您的总分最大化。最佳策略是取右边的三张牌，最终得分为 1 + 6 + 5 = 12。

约束：

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

我相信我用 memoization 编写了一个自上而下的 dp 解决方案，但是在提交代码后，我看到了 Time Limit Exceeded 错误。这个解决方案有什么问题？

class Solution {
    
    Map<String, Integer> cache = new HashMap<>();
    
    public int maxScore(int[] cardPoints, int k) {
        return max(0, cardPoints.length - 1, cardPoints, k);
    }
    
    private int max(int start, int end, int[] cardPoints, int k) {
        if (k == 1) return Math.max(cardPoints[start], cardPoints[end]);
        
        String key = "" + start + end;
        Integer value = cache.get(key);
        if (value != null) {
            return value;
        }
        
        value = Math.max(
            cardPoints[start] + max(start + 1, end, cardPoints, k - 1),
            cardPoints[end] + max(start, end - 1, cardPoints, k - 1)            
        );
        
        cache.put(key, value);
        
        return value;
    }
}

标签： algorithmdynamic-programming

解决方案

您的缓存算法存储每个中间步骤。而且有很多这样的。以选择四个值的简单情况为例，以及您的算法在每一侧选择两个值所采用的所有可能路径：

1 2 ... 4 3
1 3 ... 4 2
1 4 ... 3 2
3 4 ... 2 1
...

总共有6条不同的路径。所有这些都会导致相同的结果。总的来说，这个简单的例子已经在你的缓存中生成了 9 个状态。对于 10^5 的上限，情况看起来更糟。一共有

(10^5 + 1) * 10^5 / 2 = 5000050000

（是的，这是 50 亿个）可能的状态。并且将探索其中的每一个。因此，如果没有 TLE，您只会耗尽内存。

相反，您可以使用以下注意事项来构建更有效的算法：

  • 从任一侧选取值的顺序与最终结果无关
  • 任何不是从左侧获取的值都必须从右侧获取，反之亦然。因此，如果k必须从数组的左侧取值并从l数组的左侧k - l取值，则必须从右侧取值。

推荐阅读