2944. 购买水果需要的最少金币数

发表于 2026-01-05 分类于考点阅读次数： Waline：本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

逆序设计DP
线性DP

思路

一、问题抽象与建模

给定一个长度为 \(n\) 的数组 prices（0-index），其中：

prices[i] 表示第 \(i+1\) 个水果的购买价格；
当购买第 \(i+1\) 个水果时，可以免费获得接下来 \(i+1\) 个水果。

目标是：以最少金币获得全部水果。

二、关键观察：问题的本质是“付费起点的选择”

问题并非“每个水果买或不买”，而是：

必须选择一系列 付费购买的位置；
每次在某个位置付费后，会向右覆盖一段区间；
覆盖结束后，需要选择下一次付费的起点。

因此，该问题天然具有最优子结构，适合动态规划建模。

三、状态设计（核心）

采用 1-index 的状态定义（这是后续区间推导最清晰的形式）： \[ \boxed{ f[i] := \text{从第 } i \text{ 个水果开始，获得 } [i..n] \text{ 所有水果的最小金币数} } \]

边界条件

当 \(i = n+1\) 时，表示已经没有水果需要购买：

\[ f[n+1] = 0 \]

四、状态转移方程

若当前位于第 \(i\) 个水果（1-index）：

必须付费购买该水果，花费为 prices[i-1]；
购买第 \(i\) 个水果后，可以免费获得接下来 \(i\) 个水果；
即：第 \(i+1\) 到第 \(2i\) 个水果是免费的；
下一次仍需付费的最左位置 \(j\) 可以是：
- 在免费区间内提前付费：\(j \in [i+1, 2i]\)；
- 或免费区间吃满后再付费：\(j = 2i+1\)。

因此，下一状态的起点满足： \[ j \in [\, i+1,\ \min(n+1,\ 2i+1) \,] \] 由此得到转移方程： \[ \boxed{ f[i] = prices[i-1] + \min_{j \in [i+1,\ \min(n+1,2i+1)]} f[j] } \]

五、为什么必须倒序计算 DP？

观察状态转移可知：

\(f[i]\) 只依赖于 \(f[j]\)，其中 \(j > i\)；
即依赖方向始终指向更大的下标。

因此：

若按 \(i = 1 \to n\) 正序计算，则在计算 \(f[i]\) 时，所需的 \(f[j]\) 尚未计算；
唯一合法的计算顺序是：

\[ i = n,\ n-1,\ \dots,\ 1 \]

这正是逆序动态规划。

从本质上看，这是一张有向无环图（DAG），边从小下标指向大下标，逆序即其拓扑序。

六、朴素算法（\(O(n^2)\)）

直接按照状态转移式枚举区间最小值：

时间复杂度：\(O(n^2)\)
在本题约束 \(n \le 1000\) 下完全可行

实现代码（朴素 DP）

class Solution {
public:
    static const int maxn = 1e3 + 5;
    static const int inf = 0x3f3f3f3f;

    int minimumCoins(vector<int>& prices) {
        int n = prices.size();
        int f[maxn];

        // 边界状态：没有水果需要购买
        f[n + 1] = 0;

        // 逆序 DP
        for (int i = n; i >= 1; --i) {
            int mi = inf;
            // 枚举下一次付费起点
            for (int j = i + 1; j <= n + 1 && j <= 2 * i + 1; ++j) {
                mi = min(mi, f[j]);
            }
            // 当前必须付费购买第 i 个水果
            f[i] = mi + prices[i - 1];
        }
        return f[1];
    }
};

七、单调队列优化（\(O(n)\)）

优化目标

在转移式中： \[ \min_{j \in [i+1,\ R_i]} f[j], \quad R_i = \min(n+1, 2i+1) \] 这是一个 区间最小值查询，且满足：

\(i\) 递减时，区间右端点 \(R_i\) 也单调递减；
每个 \(f[j]\) 只会被加入一次、删除一次。

这使得 单调队列（deque） 成为可行优化手段。

八、单调队列维护的不变量

队列中存储元素 (index, f[index])，并始终满足：

下标单调递减（front → back）
- 因为 \(i\) 从 \(n\) 到 \(1\)，新元素从队尾加入；
- 队头始终是最大的下标，最先可能越界。
DP 值单调递增（front → back）
- 队头保存当前窗口内的最小 \(f[j]\)。

操作规则

删除越界元素：若 index > 2*i+1，则从队头弹出；
维护单调性：插入新值前，弹出所有 f >= 当前值 的队尾元素。

九、单调队列优化代码（\(O(n)\)）

class Solution {
public:
    int minimumCoins(vector<int>& prices) {
        int n = prices.size();
        deque<pair<int, int>> q;

        // 初始状态：f[n+1] = 0
        q.push_back({n + 1, 0});

        // 逆序遍历
        for (int i = n; i >= 1; --i) {
            // 移除右端越界的状态
            while (!q.empty() && q.front().first > 2 * i + 1)
                q.pop_front();

            // 当前状态 f[i]
            int cur = q.front().second + prices[i - 1];

            // 维护 f 值单调递增
            while (!q.empty() && q.back().second >= cur)
                q.pop_back();

            // 加入新状态
            q.push_back({i, cur});
        }

        // 最后插入的是 i = 1，对应 f[1]
        return q.back().second;
    }
};

考点

思路