如何降低购买产品最小成本问题的DP算法时间与空间复杂度

给定长度为n的整数列表cost表示产品价格，最多可使用k次discountPrice折扣方案，购买产品时有三种选择：

• 购买最左侧产品并将其从列表中移除
• 购买最右侧产品并将其从列表中移除
• 以discountPrice的价格同时购买最左侧和最右侧产品，并将两者从列表中移除

目标是计算购买所有产品的最小成本。

示例 #

示例1 #

• 输入：cost = [1, 2, 3]，discountPrice = 2，k = 1
• 预期输出：3
• 解释：
  1. 以价格1购买最左侧产品，此时cost = [2,3]
  2. 以折扣价2购买最左侧和最右侧产品，此时cost = []
     总最小成本为1+2=3

示例2 #

• 输入：cost = [9,11,13,15,17]，discountPrice = 6，k = 2
• 预期输出：21
• 解释：
  1. 以价格9购买最左侧产品，此时cost = [11,13,15,17]
  2. 以折扣价6购买最左侧和最右侧产品，此时cost = [13,15]
  3. 以折扣价6购买最左侧和最右侧产品，此时cost = []
     总最小成本为9+6+6=21

示例3 #

• 输入：cost = [1,1,1]，discountPrice = 3，k = 1
• 预期输出：3
• 解释：直接分别购买三个产品，总成本1+1+1=3（使用折扣不划算）

约束条件 #

• 1 ≤ n ≤ 10⁵
• 1 ≤ discountPrice ≤ 10⁹
• 1 ≤ k ≤ 10⁵
• 1 ≤ cost[i] ≤ 10⁹
• 输入均为正整数

当前动态规划解法 #

以下是初始的DP实现，时间复杂度为O(n²)，空间复杂度为O(n²)，无法处理n=1e5的大规模输入，需要优化时间和空间复杂度：

public static long solve(List<Integer> cost, int discountPrice, int k) {
    int n = cost.size();
    //dp[i][j] stores the minimum cost to buy products from index i to j without using discount
    long[][] dp = new long[n][n];

    // Base case: when there's only one product (i == j)
    for (int i = 0; i < n; i++) {
        dp[i][i] = cost.get(i);
    }

    // subproblems of increasing lengths
    for (int length = 2; length <= n; length++) {  
        for (int i = 0; i <= n - length; i++) {    
            int j = i + length - 1;  // right index of the subproblem

            // Option 1: Buy the leftmost
            long option1 = cost.get(i) + dp[i + 1][j];

            // Option 2: Buy the rightmost
            long option2 = cost.get(j) + dp[i][j - 1];

            // Option 3: Apply discountPrice (only if k > 0)
            long option3 = Long.MAX_VALUE;
            if (k > 0) {
                option3 = discountPrice + ((length > 2) ? dp[i + 1][j - 1] : 0);
            }

            // Store the minimum of the three options
            dp[i][j] = Math.min(option1, Math.min(option2, option3));
        }
    }
    return dp[0][n - 1];
}

public static void main(String[] args) {
    System.out.println(solve(List.of(1, 2, 3), 2, 1));  // Output: 3
    System.out.println(solve(List.of(9, 11, 13, 15, 17), 6, 2));  // Output: 21
    System.out.println(solve(List.of(1, 1, 1), 3, 1));  // Output: 3
}

优化需求 #

需要将上述算法的时间复杂度和空间复杂度同时降低，以适配n≤1e5的大规模输入场景。

内容的提问来源于stack exchange，提问作者CodeCrusader