硬币排成线 II

yingl · yingl · commit 95dba25ab8c5 · 2016-09-23T17:25:23.000+08:00
diff --git a/coins_in_a_line_ii.py b/coins_in_a_line_ii.py
@@ -0,0 +1,21 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param values: a list of integers
+    # @return: a boolean which equals to True if the first player will win
+    def firstWillWin(self, values):
+        # write your code here
+        # score[i]&#34920;&#31034;&#20174;i&#24320;&#22987;&#21040;end&#33021;&#33719;&#21462;&#30340;&#26368;&#22823;&#20540;&#12290;
+        if len(values) <= 2:
+            return True
+        score = [0] * (len(values) + 1)
+        score[-1] = 0
+        score[-2] = values[-1]
+        score[-3] = values[-2] + values[-1]
+        score[-4] = values[-3] + values[-2]
+        for i in xrange(len(values) - 4, -1, -1):
+            # &#25343;1&#20010;&#21518;&#65292;&#23545;&#26041;&#21462;1&#20010;&#25110;2&#20010;&#30340;&#24773;&#20917;&#12290;
+            score[i] = values[i] + min(score[i + 2], score[i + 3])
+            # &#25343;2&#20010;&#21518;&#65292;&#23545;&#26041;&#21462;1&#20010;&#25110;2&#20010;&#30340;&#24773;&#20917;&#12290;
+            score[i] = max(score[i], values[i] + values[i + 1] + min(score[i + 3], score[i + 4]))
+        return True if score[0] > (sum(values) - score[0]) else False
