动态规划

第一个人每次都选择   当前+之后可以拿到的  最大的值

当第一个人选择完成后，第二个人用同样的策略拿剩下的硬币中  当前+之后可以拿到的  最大的值

用dp[i][j]记录在还剩v[i]~v[j]时，先拿的人可以最多拿多少钱

用record[i][j]记录在还剩v[i]~v[j]时，先拿的人选择了哪一个 只有i和j两种可能

 

当只剩1个硬币的时候： dp[i][i] = v[i]    //只能拿这个，无悬念

当只剩2个硬币的时候： dp[i][i + 1] = max(v[i], v[i + 1])    //一定选最大的

当剩余硬币>=3个时，需要知道第二个人的策略： dp[i][j] = max(拿第一个 + 第二个人选择后剩下的能够拿到的最大值，  拿最后一个 + 第二个人选择后剩下的能够拿到的最大值）

public static int maxValue(int[]v,int n){     int[][] dp = new int[n][n];//记录i-j中可以选择的最大值     int[][] record = new int[n][n];//记录 i-j中，使得选择的结果最大的 那个 选中值的位置          for(int i=0;i
     
      =3){
   // 长度超过2时，需要考虑剩余硬币中能拿到的钱数                 //假设拿第一个                 if(record[s+1][e]==s+1)//第二个人会拿剩余的里面的第一个                     num1+=dp[s+2][e];                 else// 第二个人会拿剩余的里面的最后一个                     num1 +=dp[s+1][e-1];                              //假设拿最后一个                 if(record[s][e-1]==s)//同上                     num2 += dp[s+1][e-1];                 else //同上                     num2 +=dp[s][e-2];             }                          record[s][e]=(num1>num2)?s:e;//长度为i的选择中，选择综合值大的那个，做为选取目标             dp[s][e]=(num1>num2)?num1:num2;//         }     }          for(int i=0;i