糖果美味值 (动态规划)

描述：有 n 天，每天有一种糖果，糖果具有一定美味值；规定小美今天吃了明天就不能吃，但有 k 次机会打破规则。求这 n 天小美能吃到的最大美味值。

第一行输入 n, k；
第二行输入n天中每天的糖果的美味值。
输出最大美味值。

样例输入：
7 1
1 2 3 4 5 6 7

输出：
19

import java.util.Scanner;

/**
 * 样例输入：
 * 7 1
 * 1 2 3 4 5 6 7
 *
 * 输出：
 * 19
 */
public class Main5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 天数
        int k = sc.nextInt(); // 贪吃券的张数
        int[] nums = new int[n + 1]; // 糖果美味值数组
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }

        // dp[i][j]表示前i天用j张贪吃券能获得的最大美味值
        // i 的范围：(1, n] , j 的范围: [0, k]
        int[][] dp = new int[n + 1][k + 1];
        for (int j = 0; j <= k; j++) {
            dp[1][j] = nums[1];
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                if (j == 0) {
                    // 第i天吃，第i天不吃
                    dp[i][j] = Math.max(dp[i - 2][j] + nums[i], dp[i - 1][j]);
                } else {
                    // 第i天用券吃，第i天不用券吃，第i天不吃
                    dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1] + nums[i], dp[i - 2][j] + nums[i]),
                            dp[i - 1][j]);
                }
            }
        }

        System.out.println(dp[n][k]);
    }
}