美团的笔试题，怎么拿红包金额最大

思路：看题目应该是想考动态规划，所以第一步是建立动态转移方程

dp(i)=max( a[i]+dp(i-2)，dp(i-1))

也就是第i个位置的红包有两种方式

要么拿，拿了就不能拿i-1的红包，解是a[i]+dp(i-2)

要么不拿，不拿的解就是dp(i-1)

但是需要考虑另外一个问题，就是首尾相连

也就是拿了第一个就不能拿最后个

那么又可以分成2种方式，第一个拿与不拿

第一个拿，那么第二个和最后个就不能拿

第一个不拿，那么第二个必拿，最后个不用管拿不拿

也就是说，顺着拿一次，反着拿一次，取最大的那次就行了

import java.util.Scanner;
/*
 * 第一个位置选定，第二个位置和最后个位置不能选
 * 第一个位置不选定，则第二个位置选定，后面不用管
 * */
public class RedBag {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int N=Integer.parseInt(scanner.nextLine());
while(N-->0){
String nums=scanner.nextLine();
String bags[]=nums.split(",");
System.out.println(Math.max(getMax1(bags,bags.length-1),getMax1(reverse(bags),bags.length-1)));
}
scanner.close();
}

public static int getMax1(String bags[],int index){
if (bags.length==0) {
return 0; 
}
//第二个红包不拿
if (bags.length==1 || index==0 ||bags.length==2 || index==1) {
return Integer.parseInt(bags[0]);
}
if(index==bags.length-1){
//最后个红包不拿
return getMax1(bags, index-1);
}
return Math.max((Integer.parseInt(bags[index])+getMax1(bags, index-2)), getMax1(bags, index-1));
}
public static String[] reverse(String bags[]){
String[] b=new String[bags.length];
for(int i=0;i<bags.length;i++){
b[i]=bags[bags.length-i-1];
}
return b;
}
}

下面代码是我师兄写的版本

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for(int ii=0;ii<n;ii++){
String s = scanner.next();
String[] ss = s.split(",");
int[] hb = new int[ss.length];
for(int i=0;i<ss.length;i++){
hb[i] = Integer.parseInt(ss[i]);
}
int len = hb.length;
int[] dp1 = new int[len];
dp1[0] = hb[0];
dp1[1] = hb[0];
for(int i=2;i<len-1;i++)
dp1[i] = Math.max(dp1[i-2]+hb[i], dp1[i-1]);
int result = dp1[len-2];
for(int i=1;i<len;i++){
int[] dp2 = new int[len];
dp2[i] = hb[i];
if(i+1<len)
dp2[i+1]=dp2[i];
for(int k=i+2;k<len;k++){
dp2[k] = Math.max(dp2[k-2]+hb[k], dp2[k-1]);
}
result = Math.max(dp2[len-1], result);
}
System.out.println(result);
}
}