首页 > 代码库 > Coins in a Line II
Coins in a Line II
ref: http://www.lintcode.com/en/problem/coins-in-a-line-ii/#
有个博客说的挺好的,比九章自己写的清楚
http://www.cnblogs.com/theskulls/p/4963317.html
- 意思是这样的:
如果我们在第i个位置,那么我们有两种选择,我们要选取里面更大的
1. 我们只拿一个values[i],那么对方也是很机智的,他会试图给我们最差的结果,会选择拿一个[i+1]或者两个[i+1]&[i+2],试图给我们留更小的值,所以我们自动拿到了dp[i+2](对方拿一个)和dp[i+3](对方拿了两个)中比较小的那个,此时dp[i]_1 = values[i] + min{dp[i+2], dp[i+3]};
2. 我们拿了两个数, values[i]&values[i+1],和上一种可能里一样,机智的对手会给我们剩下dp[i+3]和dp[i+4]里比较小的那个, 此时dp[i]_1 = values[i]+values[i+1]+min{dp[i+3], dp[i+4]};
所以结果是dp[i] = max{dp[i]_1, dp[i]_2}
- 我们可以想象是从右往左推导,因为前面的结果需要确定的后面的结果
- 初始化的问题:首先我们可以人工分析出,如果有两个及以下的结果,就是都选了,如果有三个数的时候,就从左往右选前两个,因为就算不能赢也尽量给对手少点。但是到四个的时候,这个就不一定了,要根据具体的数字分析,我们不能强行初始化了。但是dp的时候又需要用到dp[i+4],所以只能多加一格,初始化成0,来辅助dp
感觉理解还是不够深入,以后多做几遍可能感觉会好一点
1 public boolean firstWillWin(int[] values) { 2 int len = values.length; 3 if(len == 0) { 4 return false; 5 } 6 if(len == 1 || len == 2) { 7 return true; 8 } 9 int[] dp = new int[len + 1]; 10 int allSum = 0; 11 dp[len] = 0; 12 dp[len - 1] = values[len - 1]; 13 dp[len - 2] = values[len - 2] + values[len - 1]; 14 dp[len - 3] = values[len - 3] + values[len - 2]; 15 allSum = dp[len - 3] + values[len - 1]; 16 for(int i = len - 4; i >= 0; i--) { 17 allSum += values[i]; 18 dp[i] = values[i] + Math.min(dp[i + 2], dp[i + 3]); 19 dp[i] = Math.max(dp[i], values[i] + values[i + 1] + Math.min(dp[i + 3], dp[i + 4])); 20 } 21 return dp[0] > allSum - dp[0]; 22 }
Coins in a Line II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。