动态规划算法题 小松鼠吃巧克力

小松鼠爱吃巧克力，巧克力可以吃一定数量，可以吃N天，每天可以多吃，或者少吃；只有前1天不吃，第2天才能多吃，也可以连续每天少吃。求小松鼠N天可以吃到的最大的巧克力的数量。
如下示例，第1行输入为天数，第2-5行，分别为每天少吃或才多吃的数量，中间用空格隔开。
示例：
6
1 3
2 15
4 7
7 34
4 22
5 13

结果：62

import java.util.Scanner;

public class SquirrelChocolate {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取天数
        int N = scanner.nextInt();
        // 存储每天少吃和多吃的巧克力数量
        int[][] a = new int[N][2];
        for (int i = 0; i < N; i++) {
            a[i][0] = scanner.nextInt();
            a[i][1] = scanner.nextInt();
        }
        // 动态规划数组，用于存储前 i 天能吃到的最大巧克力数量
        int[] dp = new int[N];
        // 初始化第一天的情况，只能选择少吃
        dp[0] = a[0][0];
        if (N > 1) {
            // 第二天的情况，要么第二天少吃加上第一天的结果，要么第二天多吃
            dp[1] = Math.max(a[1][0] + dp[0], a[1][1]);
            for (int i = 2; i < N; i++) {
                // 第 i 天的情况，有两种选择
                // 1. 第 i 天少吃，加上前一天的最大数量
                // 2. 第 i 天多吃，前提是前一天没吃，所以加上前前天的最大数量
                dp[i] = Math.max(dp[i - 1] + a[i][0], dp[i - 2] + a[i][1]);
            }
        }
        // 输出 N 天能吃到的最大巧克力数量
        System.out.println(dp[N - 1]);
        scanner.close();
    }
}

思路

1. 输入处理：

   • 借助 Scanner 类读取用户输入。
   • 首行输入代表天数 N。
   • 后续 N 行，每行有两个整数，分别表示当天少吃和多吃的巧克力数量，这些数据存于二维数组 a 中。

2. 动态规划数组：

   • 构建长度为 N 的一维数组 dp，dp[i] 代表前 i 天小松鼠能吃到的最大巧克力数量。

3. 初始化：

   • 第一天小松鼠只能选择少吃，所以 dp[0] = a[0][0]。
   • 若天数大于 1，第二天有两种选择：
     • 第二天少吃，加上第一天的最大数量，即 a[1][0] + dp[0]。
     • 第二天多吃，即 a[1][1]。
       取这两种情况的最大值作为 dp[1]。

4. 状态转移：

   • 对于第 i 天（i >= 2），有两种选择：
     • 第 i 天少吃，加上前一天的最大数量，即 dp[i - 1] + a[i][0]。
     • 第 i 天多吃，前提是前一天没吃，所以加上前前天的最大数量，即 dp[i - 2] + a[i][1]。
       取这两种情况的最大值作为 dp[i]。

5. 输出结果：

   • dp[N - 1] 就是前 N 天小松鼠能吃到的最大巧克力数量，将其输出。

此算法时间复杂度为 $O(N)$，空间复杂度也为 $O(N)$，因为使用了一个长度为 N 的数组 dp 来保存中间结果。