Leecode刷题C语言之购买水果需要的最小金币数

执行结果:通过

执行用时和内存消耗如下：

int dp(int* prices, int pricesSize, int index, int* memo) {
    if (2 * index + 2 >= pricesSize) {
        return prices[index];
    }
    if (memo[index] == -1) {
        int minValue = INT_MAX;
        for (int i = index + 1; i <= 2 * index + 2; i++) {
            minValue = fmin(minValue, dp(prices, pricesSize, i, memo));
        }
        memo[index] = prices[index] + minValue;
    }
    return memo[index];
}

int minimumCoins(int* prices, int pricesSize) {
    int *memo = (int*)malloc(pricesSize * sizeof(int));
    for (int i = 0; i < pricesSize; i++) {
        memo[i] = -1;
    }
    return dp(prices, pricesSize, 0, memo);
}

解题思路：

这段代码的目的是解决一个特定类型的动态规划问题，其中涉及到在给定的价格数组 prices 中选择若干元素，使得所选元素的总和最小，但有一个特殊的约束条件：如果你选择了价格数组中的第 i 个元素，那么你只能选择第 i+1, i+2, ..., 或 2*i+2 个元素作为下一个要选择的元素（如果存在的话）。下面详细解释这段代码的思路：

1. 定义问题：
   • 输入：一个整数数组 prices 和数组的大小 pricesSize。
   • 输出：在满足上述约束条件的前提下，从 prices 中选择若干元素所能得到的最小总和。
2. 动态规划（DP）思路：
   • 使用一个递归函数 dp(prices, pricesSize, index, memo) 来计算从 index 位置开始选择元素的最小总和。
   • memo 数组用于存储中间结果，以避免重复计算。memo[i] 存储的是从第 i 个位置开始的最小总和。
3. 递归函数 dp 的逻辑：
   • 基本情况：如果当前位置 index 之后的可选范围超出了数组边界（即 2 * index + 2 >= pricesSize），则直接返回当前位置的价格 prices[index]，因为没有后续元素可选。
   • 记忆化：检查 memo[index] 是否已经被计算过（即不等于 -1）。如果是，则直接返回 memo[index]。
   • 递归计算：如果 memo[index] 未被计算，遍历从 index + 1 到 2 * index + 2 的所有可能下一个选择位置 i，对每个位置递归调用 dp 函数，找到这些选择中的最小值 minValue。
   • 更新 memo：将当前位置 index 的最小总和更新为 prices[index] + minValue，并存储在 memo[index] 中。
   • 返回结果：返回 memo[index]。
4. 主函数 minimumCoins：
   • 分配内存并初始化 memo 数组，所有元素初始化为 -1，表示尚未计算。
   • 从位置 0 开始调用递归函数 dp，并返回其结果作为最终的最小总和。
5. 内存管理：
   • 在实际使用中，这段代码应该在适当的地方释放 memo 数组分配的内存，以避免内存泄漏。不过，在提供的代码片段中，没有显示释放内存的操作。