题解 | 取数游戏

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] A = new int[n];
        int[] B = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            B[i] = scanner.nextInt();
        }
        scanner.close();

        int[][] dp = new int[n][n];

        for (int left = 0; left < n; left++) {
            int right = left;
            int k = n - 1; 
            dp[left][right] = A[left] * B[k];
        }

        for (int len = 2; len <= n; len++) {
            for (int left = 0; left <= n - len; left++) {
                int right = left + len - 1;
                int k = n - len; 
                int takeLeft = A[left] * B[k] + dp[left + 1][right];
                int takeRight = A[right] * B[k] + dp[left][right - 1];
                dp[left][right] = Math.max(takeLeft, takeRight);
            }
        }

        System.out.println(dp[0][n - 1]);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取输入的整数n以及数组A和B的元素。
2. 初始化dp数组：处理所有长度为1的区间，直接计算对应的价值。
3. 动态规划填表：按区间长度从小到大处理，计算每个区间[left, right]的最大价值。对于每个区间，分别计算从左端和右端取数的价值，取较大者。
4. 输出结果：最终结果存储在dp[0][n-1]中，表示整个数组A的最大总价值。