我正在努力解决这个挑战：
您有一个大小为
的整数列表，代表产品成本。您有一个n，最多可以使用discountPrice次来购买产品。k您可以使用以下任一选项购买产品：
- 购买最左边的产品并将其从列表中删除
- 购买最合适的产品并将其从列表中删除
- 以
的价格购买最左边和最右边的产品，并将它们从列表中删除。discountPrice查找购买所有产品的最低价格。
示例1：
- 输入：
、cost = [1, 2, 3]和discountPrice = 2。k = 1- 预期输出：3。
说明：
- 以价格1购买最剩下的，然后
cost = [2,3]- 以折扣价3购买最左边和最右边，然后
cost = []所以购买产品的最低成本是1+2 = 3
示例2：
- 输入：
、cost = [9,11,13,15,17]、discountPrice = 6k = 2- 预期产量：21
说明：
- 购买最剩下的9，然后
cost = [11,13,15,17]- 以折扣价6购买最左边和最右边，然后
[13,15]`cost =- 以折扣价6购买最左边和最右边，然后
[]`cost =所以购买产品的最低成本是9+6+6 = 21
示例3：
- 输入：
[1,1,1]cost =折扣价格 = 3,k = 1`,- 预期：输出 = 3
限制：
- 1 <=
<= 105n- 1 <=
<= 109discountPrice- 1 <=
<= 105k- 1 <=
<= 109cost[i]输入可以是任意顺序，但必须是正整数
这是我使用 DP 的方法：
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
}
上述 DP 算法需要 O(n^2) 时间和 O(n^2) 空间，其中 n 是输入列表的大小。
我想降低时间和空间复杂度，所以我尝试使用贪心方法，但对于我的第二个测试用例，它给出了 25 作为答案，而不是 21：
public static long solve(List<Integer> cost, int discountPrice, int k) {
int left = 0;
int right = cost.size() - 1;
long totalCost = 0;
while (left <= right) {
if (left < right) {
int a = cost.get(left);
int b = cost.get(right);
if (k > 0 && discountPrice <= a && discountPrice <= b) {
totalCost += discountPrice;
left++;
right--;
k--;
} else if (a <= b) {
totalCost += a;
left++;
} else if (b < a) {
totalCost += b;
right--;
}
} else {
totalCost += cost.get(left);
left++;
}
}
return totalCost;
}
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
}
所以贪心方法并不是解决这个问题的正确方法。以较少的时间和空间复杂度解决这个问题的正确方法是什么？
您实际上可以使用您想要的任何价值的折扣，只要使用的折扣数量是对\
例如，假设您有一个包含 6 个值的列表，并且您想要对第 1、3、5 和 6 个值应用折扣。你总是可以将它表示为一个列表 [1, 0, 1, 0, 1, 1]，并且当任一侧的值为 0 时，你从这一侧以全价购买，否则你使用折扣，以便它用于两个 1。
知道了这一点，您可以对您的值进行排序，并将折扣应用于接下来的 2 个最大值，只要折扣总数小于 2*k 并且使用折扣会给您带来好处。由于排序，复杂度仅为O(n log n)。
这是它在第二个示例中的工作方式：
首先，您选择 17 和 15，这两个最大的数字并使用它们的折扣，这对您有利。然后你用13和11的折扣，这对你也有好处。您已经没有更多折扣了。
当然，您不能将折扣直接应用于算法选择的值对，但我们已经证明，只要它们的总数是对且小于 2k，就总有办法应用它们