取数游戏2（动态规划java）

取数游戏2

题目描述

给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅ax，现在希望你求出∑vi的最大值。

输入格式

第一行一个数T ，表示有T 组数据。对于每组数据，第一行一个整数 n ，接下来两行分别给出 A 数列与B 数列。

输出格式

每一组数据输出一行，最大的∑vi。

样例输入输出

样例输入

 
2
2
1 1000
2 1
5
1 3 5 2 4
1 2 3 4 5
1
2
3
4
5
6
7
8

样例输出

2001
52
1
2

数据范围

对于100的数据，保证 T≤10,1≤n≤1000,1≤ai，bi≤1000。

算法思路

首先题目中说的是每次取A数列的左端或右端，而B数列取的是第i个元素，暴力解的思路肯定就是通过回溯算法，把所有的情况尝试出来，但是这种思路肯定是会超时的，所以采用优化的算法动态规划。
首先定义dp数组的意义，因为最后要求的是A数列和B数列得出的∑vi最大值，所以可以定义为dp[0][n-1]为A数列[0 ~ n-1]得出的∑vi最大值，而dp[i][j]表示的是A数列[i ~ j]计算出来的∑vi最大值。
按照这个思路继续，继续推断递推公式，因为题干中说的是每次从A数列左端或右端取走一个数，并且乘上B数列的第i个元素，我们可以反向操作，初始的时候A数列没有元素，每次在左端或右端添加一个数，并且乘上B数列的第n-i个元素，通过这种逆向思路变可以推断出递推公式，既然每次是在左端或右端添加数，对于dp[i][j]的值来说，可能是由于dp[i+1][j]添加左端的数并且乘上B数列对应的元素得到的，也可能是dp[i][j-1]乘上B数列对应的元素得到的，取两者的最大值，那么就可以得出递推公式是dp[i][j]=max(dp[i+1][j]+B[n-j+i-1]*A[i],dp[i][j-1]+B[n-j+i-1]*A[j])，其中B[n-j+i-1]是左端或者右端添加数对应的B数列元素。
那么最后就是开始遍历dp数组来算出每个值了，其中dp数组的初始化有一个规律，就是最开始取的A数列的元素一定是乘上B数列中的最后的元素，因为dp[i]j的时候代表的意义一定是只有一个数的时候，所以在初始化dp数组的时候，让dp对角线元素等于A数列对应的元素乘上B数列最后一个元素作为初始值。

如上图，按照题干的测试案例给出的每个数组的值，其中dp数组是按照下面的元素和左面的元素来推断出来的，最后dp[0][4]便是答案。

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int T = scanner.nextInt();
        while (T>0){
            T-=1;
            //定义输入数据的初始化
            int n = scanner.nextInt();
            int []A = new int[n];
            int []B = new int[n];
            int [][]dp=new int[n][n];
            for(int i=0;i<n;++i){
                A[i]= scanner.nextInt();
            }
            for(int i=0;i<n;++i){
                B[i]= scanner.nextInt();
            }
            //让对角线上的元素等于B数组最后一个元素和A数组的第i个元素，动态规划的数组初始化
            for(int i=0;i<n;++i){
                dp[i][i]=A[i]*B[n-1];
            }
            for(int i=n-1;i>=0;i--){
                for(int j=i+1;j<n;++j){
                	//递推公式
                    dp[i][j]=Math.max(dp[i+1][j]+B[n-j+i-1]*A[i],dp[i][j-1]+B[n-j+i-1]*A[j]);
                }
            }
            System.out.println(dp[0][n-1]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34