使用动态规划的具有分区约束的最大和子数组

Question

问题陈述： 给定一组 n 个面额的硬币（可能重复，随机顺序），以及一个数字 k。单个玩家按以下方式玩游戏：玩家可以选择连续挑选 0 到 k 个硬币，但必须让下一个硬币不被挑选。以这种方式给出最大数量的硬币he/she可以收集。

输入： 第一行分别包含2个space分隔的整数n和x，表示 n - 数组的大小 x - Window 尺寸

输出： 一个整数，表示玩家可以获得的最大总和。

工作解决方案Link: Ideone

long long solve(int n, int x) {
    if (n == 0) return 0;
    long long total = accumulate(arr + 1, arr + n + 1, 0ll);
    if (x >= n) return total;
    multiset<long long> dp_x;
    for (int i = 1; i <= x + 1; i++) {
        dp[i] = arr[i];
        dp_x.insert(dp[i]);
    }
    for (int i = x + 2; i <= n; i++) {
        dp[i] = arr[i] + *dp_x.begin();
        dp_x.erase(dp_x.find(dp[i - x - 1]));
        dp_x.insert(dp[i]);
    }
    long long ans = total;
    for (int i = n - x; i <= n; i++) {
        ans = min(ans, dp[i]);
    }
    return total - ans;
}

谁能解释一下这段代码是如何工作的，即第 19 行是如何工作的？ Ideone 解决方案中的 12-26 是否给出了正确答案？

我用笔和纸干了运行代码，发现它给出了正确的答案，但无法弄清楚所使用的算法（如果有的话）。有人可以向我解释第 12-26 行是如何产生正确答案的吗？这里有什么技术或算法吗？

我是 DP 的新手，所以如果有人能指出与此类问题相关的教程（YouTube 视频等），那也很好。谢谢。

Answer 1

看来思路是转换问题- 您必须在连续不超过x+1个硬币中至少选择一个硬币，并使其最小化 .那么原始问题的答案就是[所有值的总和] - [新问题的答案]。

然后我们准备谈谈动态规划。让我们为 f(i) 定义一个递归关系，这意味着“新问题的部分答案考虑第一个到 i-th 个硬币，并且选择了 i-th 个硬币”。（抱歉描述不当，欢迎编辑）

f(i) = a(i)                                    : if (i<=x+1)
f(i) = a(i) + min(f(i-1),f(i-2),...,f(i-x-1))  : otherwise

where a(i) is the i-th coin value

我逐行添加了一些注释。

// NOTE f() is dp[] and a() is arr[]

long long solve(int n, int x) {
    if (n == 0) return 0;
    long long total = accumulate(arr + 1, arr + n + 1, 0ll); // get the sum
    if (x >= n) return total;
    multiset<long long> dp_x; // A min-heap (with fast random access)
    for (int i = 1; i <= x + 1; i++) { // For 1 to (x+1)th,
        dp[i] = arr[i];                // f(i) = a(i)
        dp_x.insert(dp[i]); // Push the value to the heap
    }
    for (int i = x + 2; i <= n; i++) {  // For the rest, 
        dp[i] = arr[i] + *dp_x.begin(); // f(i) = a(i) + min(...)
        dp_x.erase(dp_x.find(dp[i - x - 1])); // Erase the oldest one from the heap
        dp_x.insert(dp[i]); // Push the value to the heap, so it keeps the latest x+1 elements
    }
    long long ans = total;
    for (int i = n - x; i <= n; i++) { // Find minimum of dp[] (among candidate answers)
        ans = min(ans, dp[i]);
    }
    return total - ans;
}

另请注意，multiset 用作 min-heap。然而，我们还需要快速 random-access（擦除旧的）并且 multiset 可以在对数时间内完成。所以，总的时间复杂度是O(n log x).

使用动态规划的具有分区约束的最大和子数组

Max Sum Subarray with Partition constraint using Dynamic Programming

c++

dynamic-programming