文章

[LeetCode] 每日一题 2944. 购买水果需要的最少金币数

题目链接

https://leetcode.cn/problems/minimum-number-of-coins-for-fruits

题目描述

给你一个 下标从 1 开始的 整数数组 prices ,其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。

水果超市有如下促销活动:

  • 如果你花费 prices[i] 购买了下标为 i 的水果,那么你可以免费获得下标范围在 [i + 1, i + i] 的水果。

注意 ,即使你 可以 免费获得水果 j ,你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。

请你返回获得所有水果所需要的 最少 金币数。

示例输入

示例 1

输入:prices = [3,1,2]

输出:4

解释:
用 prices[0] = 3 个金币购买第 1 个水果,你可以免费获得第 2 个水果。
用 prices[1] = 1 个金币购买第 2 个水果,你可以免费获得第 3 个水果。
免费获得第 3 个水果。
请注意,即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励,但您购买它是为了获得其奖励,这是更优化的。

示例 2

输入:prices = [1,10,1,1]

输出:2

解释:
用 prices[0] = 1 个金币购买第 1 个水果,你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 1 个金币购买第 3 个水果,你可以免费获得第 4 个水果。
免费获得第 4 个水果。

示例 3

输入:prices = [26,18,6,12,49,7,45,45]

输出:39

解释:
用 prices[0] = 26 个金币购买第 1 个水果,你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 6 个金币购买第 3 个水果,你可以免费获得第 4,5,6(接下来的三个)水果。
免费获得第 4 个水果。
免费获得第 5 个水果。
用 prices[5] = 7 个金币购买第 6 个水果,你可以免费获得第 7 和 第 8 个水果。
免费获得第 7 个水果。
免费获得第 8 个水果。
请注意,即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励,但您购买它是为了获得其奖励,这是更优化的。

提示

  • 1 <= prices.length <= 1000

  • 1 <= prices[i] <= 10^5

解题思路

我们需要最小化购买水果的总花费,可以采用递归的方式来进行分治。以下是思路分析:

  1. 定义子问题

    • 定义 dfs(i) 表示在购买第 i 个水果的前提下,获得第 i 个及其后面的水果所需要的最少金币数

    • 如果购买第 i 个水果,那么从 i + 12 * i 的水果都是免费的。然后,我们需要选择一个后续购买的水果 j,并递归地计算从第 j 个水果开始需要的最小金币数

  2. 状态转移

    • 对于每一个 i,我们需要枚举购买的下一个水果 j,其范围为 [i + 1, 2 * i + 1]。然后计算 dfs(j) 的最小值,再加上购买第 i 个水果的花费 prices[i]

    • 递归终止条件:当 i 达到 ⌊n / 2⌋ 时,后面的水果都可以免费获得

  3. 记忆化搜索优化

    • 由于存在重叠子问题,我们可以使用记忆化搜索来保存已经计算过的状态,避免重复计算

代码实现

class Solution {
    public int minimumCoins(int[] prices) {
        int[] memory = new int[(prices.length + 1) / 2];
        return dfs(1, prices, memory);
    }

    public int dfs(int index, int[] prices, int[] memory) {
        if (index * 2 >= prices.length) {
            return prices[index - 1];
        }
        if (memory[index] != 0) {
            return memory[index];
        }
        int res = Integer.MAX_VALUE;
        for (int j = index + 1; j <= index * 2 + 1; j++) {
            res = Math.min(res, dfs(j, prices, memory));
        }
        return memory[index] = res + prices[index - 1];
    }
}

复杂度分析

  • 时间复杂度

    • 由于每次递归都枚举范围 [i + 1, 2 * i + 1] 内的每个 j,因此每个状态会遍历最多 O(n)

    • 总的时间复杂度为 O(n^2),其中 n 为水果数量

  • 空间复杂度

    • 递归的深度最多为 O(n),因为递归从 1⌊n / 2⌋ 逐步向后推进

    • 需要额外的空间来存储记忆化数组 memory,空间复杂度为 O(n)

总结

今天这道题目让我对递归和记忆化搜索有了更深的理解。题目本身的关键在于如何处理促销活动的规则,特别是如何利用递归去计算每个水果购买后的最优选择。通过递归分解问题,把目标从“获得所有水果最少花费”转化成了“在购买某个水果后,剩余水果的最少花费”,从而逐步求解

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0