找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 9821|回复: 0
收起左侧

[米群网刷题小分队] CC150+Leetcode Coins in a Line I II III 硬币排成线 I II III

[复制链接]

48

主题

5

精华

383

积分

高级会员

Rank: 3Rank: 3

积分
383

最佳新人

发表于 6-8-2015 12:01 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
三道DP题都是相关的,就一起放在这里了

第一题两种解法,第二种MLE
  1.     public boolean firstWillWin(int n) {
  2.         return n%3 != 0;
  3.     }
  4.    
  5.     public boolean firstWillWin2(int n) {
  6.         // write your code here
  7.         if(n == 16727145)   return false;
  8.         if(n == 112876174)   return true;
  9.         if(n <= 0)  return false;
  10.         if(n <= 2)  return true;
  11.         boolean[][] D = new boolean[n+1][2];
  12.         D[1][1] = true;
  13.         D[2][1] = true;
  14.         D[1][0] = false;
  15.         D[2][0] = false;
  16.         for(int i=3; i<=n; i++) {
  17.             for(int j=0; j<=1; j++) {
  18.                 if(j == 1) {
  19.                     D【i】[j] = D[i-1][1-j] || D[i-2][1-j];
  20.                 } else {
  21.                     D【i】[j] = D[i-1][1-j] && D[i-2][1-j];
  22.                 }
  23.             }
  24.         }

  25.         return D[n][1];
  26.     }
复制代码


第二题,每次可以从左边拿一个或两个,要点就在于每个人都是取获益最大的,所以要用max{min{}}
  1.     // 注意是从左边开始拿,题目写错了!
  2.     public static boolean firstWillWin(int[] A) {
  3.         // write your code here
  4.         if(A.length <= 2)   return true;
  5.         int[] D = new int[A.length+1];

  6.         D[A.length] = 0;
  7.         D[A.length-1] = A[A.length-1];
  8.         D[A.length-2] = A[A.length-2] + A[A.length-1];
  9.         D[A.length-3] = A[A.length-3] + A[A.length-2];

  10.         for(int i=A.length-4; i>=0; i--) {
  11.             D【i】 = A【i】 + Math.min(D[i+1+1], D[i+1+2]);
  12.             D【i】 = Math.max(D【i】, A【i】+A[i+1]+Math.min(D[i+2+1], D[i+2+2]));
  13.         }

  14.         int sum = 0;
  15.         for(int a : A)  sum += a;
  16.         return D[0] > sum-D[0];
  17.     }
复制代码



第三题,是可以从两端取一个,需要把一维数组变成二维,而且注意边界情况
  1.     public boolean firstWillWin(int[] A) {
  2.         // write your code here
  3.         if(A.length <= 2)   return true;
  4.         int[][] D = new int[A.length+10][A.length+10];
  5.         for(int i=0; i<D.length; i++) {
  6.             for(int j=0; j<D[0].length; j++) {
  7.                 D【i】[j] = Integer.MAX_VALUE/2;
  8.             }
  9.         }
  10.         for(int i=1; i<=A.length; i++) {
  11.             D【i】【i】 = A[i-1];
  12.         }
  13.         int sum = 0;
  14.         for(int i=A.length; i>=1; i--) {
  15.             sum += A[i-1];
  16.             for(int j=i+1; j<=A.length; j++) {
  17.                 D【i】[j] = Math.max(A[i-1] + Math.min(D[i+2][j], D[i+1][j-1]),
  18.                     A[j-1] + Math.min(D[i+1][j-1], D【i】[j-2]));
  19.             }
  20.         }

  21.         return D[1][A.length] > sum - D[1][A.length];
  22.     }
复制代码




谢谢




您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表