题解 | 跳跳跳

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[2 * n];
        for (int i = 0; i < n; i++){
            nums[i] = sc.nextInt();
            nums[i + n] = nums[i];
        }

        // dp[1][r] 表示在区间[1][r] 内完成跳跃所能获得的最高分
        long[][] dp = new long[2 * n][2 * n];

        // 初始化：单个点，第一步
        for (int i = 0; i < 2 * n; i++) {
            dp[i][i] = nums[i];
        }


        // 枚举区间的长度 从 2 到 n
        for (int len = 2; len <= n; len++) {
            // 枚举左端点1eft
            for (int left = 0; left <= 2 * n - len; left++) {
                int right = left + len - 1;
                // 两种情况：最后一步(len)跳左边，最后一步(len)跳右边
                long option1 = dp[left + 1][right] + (long) len * nums[left];
                long option2 = dp[left][right - 1] + (long) len * nums[right];
                dp[left][right] = Math.max(option1, option2);
            }
        }

        // 在所有长度为 n 的区间中找到最大值
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i][i + n - 1]);
        }
        System.out.println(ans);
    }
}

这是一道动态规划问题

步骤一：初始化第一跳的得分，第一部的得分是固定的，就是每个格子的分数

步骤二：第二跳的得分根据第一跳的得分，再加上第二跳的得分就是第二跳的总得分，但是第二跳可能是跳左边或者跳右边，进行判断，看看哪一跳的总得分相加更高

依次类推，最后在根据间隔为【n - 1】判断跳了n次总得分哪个最高