1.更改石子游戏模板并解析边界值（java代码）

	//石子游戏模板代码
	for(int len = 2;len<=n;len++) //枚举长度
	for(int l = 1;l+len-1<=n;l++){
		int r = l+len -1;
		dp[l,r] = INF;
		for(int k = l;k<r;++k) dp[l,r] = min(dp[l,r],dp[l,k]+dp[k+1,r]+sum[l,r]);
	}

看了很多的题解，发现有些解答边界值是像下面这个代码，

                dp[i][i] = a[i]*b[n];
            }

但是不解释具体为什么是a[i]*b[n]，为什么不是a[i]*b[i]或者是其他的下面我来给大家一步一步推导. 假设dp[1,n]是1-n的最小代价那么肯定是如下关系 dp[1,n] = max{dp[1,n-1]+a[n]*b[1].dp[2,n]+a[1]*b[1]} 有的同学可能会疑惑，为什么不是b[n]而是b[1]。是这样的，a[1]和a[n]两个位置其中之一只能在第一次去取，对应的第一次代价就是b[1]，所以乘的是b[1]而不是b[n] 而dp[1,n-1] = max{dp[2,n-1]+a[1]*b[2],dp[1,n-2] + a[n-1]*b[2]} dp[2,n] = max{dp[2,n-1]+a[n]*b[2],dp[3,n] + a[2]*b[2]} 以此类推b里面的数字 = n-(j-i)=n-(len-1) 当j=i时，b里面的数字=n dp[i][i] = a[i]*b[n] java代码如下

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        while (t-->0){
            int n = input.nextInt();
            int[] a = new int[n+2];
            int[] b = new int[n+2];
            for (int i = 1; i <=n ; i++) {
                a[i] = input.nextInt();
            }
            for (int i = 1; i <=n ; i++) {
                b[i] = input.nextInt();
            }
            int[][] dp = new int[n+2][n+2];
            for(int i=1;i<=n;i++){ 
                dp[i][i] = a[i]*b[n];
            }
            
            for(int len=2;len<=n;len++)
            {
                for(int l = 1; l+len-1<=n; l++)
                
                {
                    int r = l+len-1;
                    dp[l][r] = Math.max(dp[l+1][r] + a[l]*b[n-len+1],
                                                        dp[l][r-1]+a[r]*b[n-len+1]);
                }
            }
            System.out.println(dp[1][n]);
        }
    }
}