力扣每日一题2218

题目描述：

解析：动态规划

package January;

import java.util.Arrays;
import java.util.List;

/**
 * @author hxw
 * @version 1.0
 * @date 2025/1/21 19:42
 * @description: 2218. 从栈中取出 K 个硬币的最大面值和 困难
 */
public class twenty_one {
    public static void main(String[] args) {
        // 创建 List<List<Integer>> 类型的参数
        List<List<Integer>> piles = Arrays.asList(
                Arrays.asList(100, 3)
                , Arrays.asList(100)
        );
        int k = 2;
        int result = Solution.maxValueOfCoins(piles, k);
        System.out.println("Result: " + result);
    }



    class Solution {

        public static int maxValueOfCoins(List<List<Integer>> piles, int k) {
            int n = piles.size();
            // dp[i][j] 表示 前 i 个数组中取 j 个的最大值，返回值 dp[n][k]
            int[][] dp = new int[2][k + 1];
            dp[0][0] = 0;
            for (int i = 1; i <= n; i++) {

                int[] presum = new int[piles.get(i - 1).size() + 1];
                for (int j = 1; j < presum.length; j++) {
                    presum[j] = presum[j - 1] + piles.get(i - 1).get(j - 1);
                }

                for (int j = 1; j <= k; j++) {
                    dp[i % 2][j] = 0;
                    for (int kk = 0; kk <= piles.get(i - 1).size() && kk <= j; kk++) {
                        dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - kk] + presum[kk]);
                    }
                }
            }
            return dp[n % 2][k];
        }
    }
}