一：
题目描述A、B两伙马贼意外地在一片沙漠中发现了一处金矿，双方都想独占金矿，但各自的实力都不足以吞下对方，经过谈判后，双方同意用一个公平的方式来处理这片金矿。处理的规则如下：他们把整个金矿分成n段，由A、B开始轮流从最左端或最右端占据一段，直到分完为止。
马贼A想提前知道他们能分到多少金子，因此请你帮忙计算他们最后各自拥有多少金子?（两伙马贼均会采取对己方有利的策略）
输入
测试数据包含多组输入数据。输入数据的第一行为一个正整数T(T<=20)，表示测试数据的组数。然后是T组测试数据，每组测试数据的第一行包含一个整数n，下一行包含n个数（n <= 500 ），表示每段金矿的含金量，保证其数值大小不超过1000。
样例输入
2
6
4 7 2 9 5 2
10
140 649 340 982 105 86 56 610 340 879
输出
对于每一组测试数据，输出一行"Case #id: sc1 sc2"，表示第id组数据时马贼A分到金子数量为sc1，马贼B分到金子数量为sc2。详见样例。
样例输出
Case #1: 18 11
Case #2: 3206 981
时间限制 C/C++语言：1000MS 其它语言：3000MS 内存限制 C/C++语言：65536KB 其它语言：589824KB
一：递归解法：
设f(L,R)表示从L到R的这一串数字中，先手所能获得的最大金矿价值。则
代码如下
package com.itheima.threesixzero; import java.util.Scanner; /** * 博弈问题 * 分金子 * @author Dell * */ public class Test2 { public static int f(int[] a,int start,int end) { if(start<0||end>a.length-1||start>end) return -1; else if(start==end) return a[start]; else { int sum=0; for(int i=start;i<=end;i++) sum=sum+a[i]; return Math.max(sum-f(a,start+1,end),sum-f(a,start,end-1)); } } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[][] result=new int[n][2]; int k=1; while(k<=n){ int num=sc.nextInt(); int[] a=new int[num]; int t=0; for(int i=0;i<a.length;i++) { a[i]=sc.nextInt(); t=t+a[i]; } int sum=f(a,0,a.length-1); result[k-1][0]=sum; result[k-1][1]=t-sum; k++; } for(int i=0;i<n;i++) { System.out.println("Case #"+(i+1)+": "+result[i][0]+" "+result[i][1]); } } }但是当数据规模一大，很容易超时， 所以改用动态规划做法，避免很多子问题的重复计算：
设dp[i][j]表示从i到j，先手所能获得的最大价值：
于是：
package com.itheima.threesixzero; import java.util.Scanner; public class Test3 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int num=sc.nextInt(); int[] a=new int[num]; int t=0; for(int i=0;i<a.length;i++) { a[i]=sc.nextInt(); t=t+a[i]; } int[][] dp=new int[num+1][num+1]; int[] sum=new int[num+1]; // for(int i=1;i<num+1;i++) { dp[i][i]=a[i-1]; sum[i]=sum[i-1]+a[i-1]; } for(int i=num-1;i>=1;i--) for(int j=i;j<num+1;j++) { int x=sum[j]-sum[i-1]-dp[i+1][j]; int y=sum[j]-sum[i-1]-dp[i][j-1]; dp[i][j]=Math.max(x, y); } System.out.println(dp[1][num]+" "+(t-dp[1][num])); } }
剪气球串（360公司2017春招真题）
题目描述小明买了一些彩色的气球用绳子串在一条线上，想要装饰房间，每个气球都染上了一种颜色，每个气球的形状都是各不相同的。我们用1到9一共9个数字表示不同的颜色，如12345则表示一串5个颜色各不相同的气球串。但小明希望得到不出现重复颜色的气球串，那么现在小明需要将这个气球串剪成多个较短的气球串，小明一共有多少种剪法？如原气球串12345的一种是剪法是剪成12和345两个气球串。
注意每种剪法需满足最后的子串中气球颜色各不相同（如果满足该条件，允许不剪，即保留原串）。两种剪法不同当且仅当存在一个位置，在一种剪法里剪开了，而在另一种中没剪开。详见样例分析。
输入
第一行输入一个正整数n（1≤n≤100000），表示气球的数量。
第二行输入n个整数a1，a2，a3...an，ai表示该气球串上第i个气球的颜色。对于任意i，有1≤ai≤9。
样例输入
3
1 2 3
输出
输出一行，第一行输出一个整数，表示满足要求的剪法，输出最终结果除以1000000007后的余数。
样例输出
4
时间限制 C/C++语言：2000MS 其它语言：4000MS 内存限制 C/C++语言：131072KB 其它语言：655360KB
这同样是一道动态规划问题，设置dp[i]为前i个气球可以剪到的最大子串数量，则
package com.itheima.threesixzero; import java.util.HashSet; import java.util.Scanner; import java.util.Set; /** * 剪气球串 * @author Dell * */ public class Test4 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] a=new int[n]; for(int i=0;i<a.length;i++) { a[i]=sc.nextInt(); } int[] dp=new int[n+1]; dp[0]=1; for(int i=1;i<=n;i++) { Set<Integer> set=new HashSet<>(); for(int j=i;j>=1;j--) { if(set.contains(a[j-1])) { break; } else { set.add(a[j-1]); dp[i]=(dp[i]+dp[j-1])00000007; } } } System.out.println(dp[n]); } }
