区间dp3

题目解析

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i <n ; i++) {
            a[i] = input.nextInt();
        }
        for (int i = 0; i <n ; i++) {
            b[i] = input.nextInt();
        }
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++)
        {
            dp[i][i]=a[i]*b[n-1];//i-i的最优解
        }

        for(int i=n-1;i>=0;i--)
        {
            for(int j=i+1; j<n; j++)
            {
                dp[i][j]=Math.max(a[i]*b[n-(j-i+1)]+dp[i+1][j],a[j]*b[n-(j-i+1)]+dp[i][j-1]);//i--j的最优解为：a拿前一个且b拿第n-(j-i+1)个，或者a拿最后一个，b拿n-(j-i+1)，求最大值即可
            }
        }
        System.out.println(dp[0][n-1]);
    }
}