Find minimum cost to buy products

I am trying to solve this challenge:

You have a list of integers of size n, that represents costs of products. You have a discountPrice which can be used at most k times, to buy products.

You can buy the products using any one of below options:

1. Buy left most product and remove it from list
2. Buy right most product and remove it from list
3. Buy left most and right most products at a price of discountPrice, and remove both from list.

Find the minimum price to purchase all products.

Example 1:

• Input: cost = [1, 2, 3], discountPrice = 2, and k = 1.
• Expected output: 3.

Explanation:

1. Purchase left most at price 1, then cost = [2,3]
2. Purchase left most and right most at discountPrice 3, then cost = []

So minimum cost to buy products is 1+2 = 3

Example 2:

• Input: cost = [9,11,13,15,17], discountPrice = 6, k = 2
• Expected output: 21

Explanation:

1. Purchase left most at 9, then cost = [11,13,15,17]
2. Purchase left most and right most at discountPrice 6, then cost = [13,15]`
3. Purchase left most and right most at discountPrice 6, then cost = []`

So minimum cost to buy products is 9+6+6 = 21

Example 3:

• Input: cost = [1,1,1], discountPrice = 3, k = 1`
• Expected: output = 3

Constraints:

• 1 <= n <= 10⁵
• 1 <= discountPrice <= 10⁹
• 1 <= k <= 10⁵
• 1 <= cost[i] <= 10⁹

Input can be in any order, but has positive integers

Here is my approach using 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
    }

The above DP algorithm is taking O(n^2) time and O(n^2) space where n is the size of input list.

I want to reduce both time and space complexity.

You can actually use your discount on any values you want, as long as the number of discounts used is pair\

For example, consider you have a list of 6 values and you want to apply discounts to the 1st, 3rd, 5th and 6th values. You can always represent it as a list [1, 0, 1, 0, 1, 1], and just when a value on either side is 0, you buy at full price from this side, else you use the discount so that it is used on two 1's.
Knowing this, you can just sort your values, and apply the discount to the next 2 biggest values as long as the total number of discounts is less than 2*k and using the discount will benefit you. The complexity is only O(n log n) because of sorting. Here's how it would work on your second example:
first you choose 17 and 15, the 2 biggest numbers and use the discount on them, which benefits you. Then you use the discount on 13 and 11, which also benefits you. You have no more discounts left.
Of course, you cannot apply the discounts directly to the pairs of values chose by the algorithm, but we have demonstrated that there will be always a way to apply them as long as their total number is pair and less than 2k