Coins in a line系列问题

此题是lintcode上的一个系列，总共三道，其中第一题在LeetCode上有一道原题，并且此题有一个更优的O(1)算法（利用数学规律推导），这里不详述

第二题则是一个纯博弈类动态规划，此题主要是通过树型图发现当前能拿到的最高硬币价值和之前几个状态的联系，另外参考矩阵dp的初始化，以及最后的判胜负的标准（总和大过所有价值的一半）是关键问题，下面是代码

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
        n = len(values)
        dp = [0] * (n + 1)
        ref = [False] * (n + 1)
        return 2 * self.search(values, n, dp, ref, n) > sum(values)

    def search(self, values, n, dp, ref, length):
        if ref[n]:
            return dp[n]

        ref[n] = True

        if n == 0:
            dp[n] = 0
        elif n == 1:
            dp[n] = values[length - 1]
        elif n == 2:
            dp[n] = values[length - 2] + values[length - 1]
        elif n == 3:
            dp[n] = values[length - 3] + values[length - 2]
        else:
            a = self.search(values, n - 2, dp, ref, length)
            b = self.search(values, n - 3, dp, ref, length)
            c = self.search(values, n - 4, dp, ref, length)
            dp[n] = max(min(a, b) + values[length - n],
                        min(b, c) + values[length - n + 1] +
                        values[length - n])

        return dp[n]

第三题则是一个博弈类和区间类的混合型题目，LeetCode题目地址，Lintcode题目地址

这两道题其实基本上是一样的，比较不同的地方是II是一个只能从一侧取硬币，然后硬币数量可一可二的题，而III是一个可以从左右两侧取硬币但都只能取一枚的题，所以他们的区别基本就在记忆化搜索带入的参数不太相同罢了，另外因为此题需要二维矩阵的存在也能看出来一些区间DP的性质，这也是和II不太一样的地方

class Solution:
    # @param values: a list of integers
    # @return: a boolean which equals to True if the first player will win
    def firstWillWin(self, nums):
        # write your code here
        n = len(nums)
        if not n:
            return False

        res = [([0] * n) for _ in xrange(n)]
        ref = [([False] * n) for _ in xrange(n)]

        return 2 * self.helper(0, n - 1, ref, res, nums) >= sum(nums)

    def helper(self, i, j, ref, res, nums):
        if ref[i][j]:
            return res[i][j]

        ref[i][j] = True
        if i == j:
            res[i][j] = nums[i]
            return res[i][j]
        elif i + 1 == j:
            res[i][j] = max(nums[i], nums[j])
            return res[i][j]
        elif i > j:
            return res[i][j]
        else:
            a = self.helper(i + 2, j, ref, res, nums)
            b = self.helper(i + 1, j - 1, ref, res, nums)
            c = self.helper(i, j - 2, ref, res, nums)
            res[i][j] = max(min(a, b) + nums[i], min(b, c) + nums[j])
            return res[i][j]

最近都不是很习惯写记忆化搜索了，而实际上区间类的DP虽然初始化确实比坐标型麻烦一点，但基本上还是有规律可寻的，区间类的DP矩阵只会用半边，而初始化状态就是左对角线，我们每次应该逐列遍历状态，且起点都是对角线上的点，这样写for循环比记忆化搜索的代码就要短很多了

class Solution(object):
    def PredictTheWinner(self, values):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(values)
        dp = [[0] * n for _ in xrange(n)]
        for i in xrange(n):
            dp[i][i] = values[i]
            if i:
                dp[i - 1][i] = max(values[i - 1], values[i])

        for i in xrange(2, n):
            for j in xrange(i - 2, -1, -1):
                dp[j][i] = max(min(dp[j + 1][i - 1], dp[j + 2][i]) + values[j], \
                                min(dp[j + 1][i - 1], dp[j][i - 2]) + values[i])

        return dp[0][n - 1] >= float(sum(values)) / 2

其实不用单独初始化

class Solution(object):
    def PredictTheWinner(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        dp = [[0] * n for _ in xrange(n)]

        for i in xrange(n):
            for j in xrange(i, -1, -1):
                if i == j:
                    dp[j][i] = nums[j]
                elif j + 1 == i:
                    dp[j][i] = max(nums[j], nums[i])
                else:
                    dp[j][i] = max(min(dp[j + 1][i - 1], dp[j + 2][i]) + nums[j],\
                                    min(dp[j + 1][i - 1], dp[j][i - 2]) + nums[i])

        return dp[0][n - 1] >= float(sum(nums)) / 2