SnapChat 电面挂经

满城尽带黄金甲 发表于 2016-9-5 02:21
有个问题，如果是[5, 7, 8, 5]这个subarray， B先拿，那么它会拿哪个？如果B拿第一个5，那么A可以在剩下的 ...

你考虑的这个跟我想法一样, 所以我对上面的解法有一些疑问.

我觉得如果轮到B取的时候, 如果coin[i] == coin[j], 此时我们不能默认B就取 i 或 j (上面的解法把== 归到了> or < 的情况, 我觉得是不对的), 而是我们应该假定B取得结果使得A剩余的能取得的最大值最小.

个人解法:

1. public static int takeMost(int[] coins){
   
2.                 int n = coins.length;
   
3.                 int[][] dp = new int[n+2][n+2];
   
4.                 for(int j=0; j<n; j++){
   
5.                         for(int i=j; i>=0; i--){
   
6.                                 if(i >= j-1){
   
7.                                         dp[i][j] = Math.max(coins[i], coins[j]);
   
8.                                 } else{         // <----  i <= j - 2
   
9.                                         // A takes coins[i]
   
10.                                         int opt1 = coins[i];
    
11.                                         if(coins[i+1] > coins[j]){
    
12.                                                 opt1 += dp[i+2][j];
    
13.                                         } else if (coins[i+1] < coins[j]){
    
14.                                                 opt1 += dp[i+1][j-1];
    
15.                                         } else{
    
16.                                                 opt1 += Math.min(dp[i+2][j], dp[i+1][j-1]);
    
17.                                         }
    
18.                                         // A takes coins[j]
    
19.                                         int opt2 = coins[j];
    
20.                                         if(coins[i] > coins[j-1]){
    
21.                                                 opt2 += dp[i+1][j-1];
    
22.                                         } else if(coins[i] < coins[j-1]){
    
23.                                                 opt2 += dp[i][j-2];
    
24.                                         } else {
    
25.                                                 opt2 += Math.min(dp[i][j-2], dp[i+1][j-1]);
    
26.                                         }
    
27.                                         dp[i][j] = Math.max(opt1, opt2);                                               
    
28.                                 }                                       
    
29.                         }
    
30.                 }
    
31.                 return dp[0][n-1];
    
32.         }

复制代码

recursion + memorization
时间复杂度应该是O(n^2) 应该是最优解吧
个人愚解，大家看看是这样的吗

ykwwind 发表于 2016-4-19 07:01
补充内容 (2016-4-19 07:02):
感觉最近都是这种路数..........

最近是什么路数？没看出来啊。。

Leetcode 486