leetcode 877

此題雖然題目不好，但是Discuss中的solution非常好。mark，mark。這題我的解法是遞歸。因為看到了兩者都是采用最優的解法。是以很自然地就能夠想到問題可以分解為更小的子問題。結果我用遞歸做，逾時了。。。。後來看别人的解法，才想到dp(太久不用dp,都完全忽略了這種解法，自己對dp的掌握也不夠熟練)。當然也看到了直接傳回True的解法，下面我對這幾種方法來分析一下：

首先是遞歸解法，思想如下，我是認為從一個大問題到子問題需要兩次拿取。是以兩次拿的情況有四種，AB都拿左邊，A左B右，A右B左，AB都拿右邊。是以得到了以下的遞歸解法。

class Solution:

    def stoneGame(self, piles):

        """

        :type piles: List[int]

        :rtype: bool

        """

        total = 0

        for i in piles:

            total += i

        def score(piles):

            if len(piles) == 2:

                return max(piles[0],piles[1])

            case1 = score(piles[2:])

            case2 = score(piles[:-2])

            case3 = score(piles[1:-1])

            return max(case1+piles[0],case2+piles[-1],case3+piles[0],case3+piles[-1])

        temp  = score(piles)

        if temp > (total -temp):

            return True

        else:

            return False

       第二種是直接傳回True。一開始我也有這種想法，discuss給出了明确的解釋，非常贊。原理就是先選的那個可以一直選擇奇數位的stone或者是偶數位的stone。比如A先選了pile[0],那麼如果B選擇pile[1],A就可以選擇pile[2],如果B選擇了pile[n-1],A就可以選擇pile[n-2],也就是說A可以選擇是以的偶數位的stone。同理，如果A一開始選擇的是pile[n-1]，那麼A就可以選擇所有奇數位的stone。又因為總數是奇數，是以偶數位stone的總和，和奇數位stone的總和，肯定有一個高一個低，又因為A總是采用最優的政策，是以A隻要選擇了總和高的stone，A就一定會赢。

      第三種是通過采用動态規劃的方法。因為原問題可以拆分成子問題，是以采用dp.通過dp也可以處理奇數位stone的情況等等。令dp[i][j]表示的是從第i位到第j位，首先選擇的人最多能比後面選擇的人多多少個stone.那麼對于dp[i][j]=max(pile[i]-dp[i+1][j],pile[j]-dp[i][j-1]),也就是我有兩種選擇，一種選前面的，那麼現在我就有pile[i]個stone了，那麼對于剩下的piles，相當于對方先選，因為雙方都會選擇最優政策，是以對方會比自己多dp[i+1][j]個stone，那麼在i，j這個區間内，自己就比對方多pile[i]-dp[i+1][j]個stone。後者同理。附代碼：

class Solution:

    def stoneGame(self, piles):

        """

        :type piles: List[int]

        :rtype: bool

        """

        n = len(piles)

        dp = [[0]*n for i in range(n)]

        for i in range(n):

            dp[i][i] = piles[i]

        for d in range(1,n):

            for j in range(n-d):

                dp[j][j+d] = max(piles[j]-dp[j+1][j+d], piles[j+d]-dp[j][j+d-1])

        return dp[0][n-1] > 0

最後一種還是DP的方法，不過空間複雜度是O(n)，這種方法的dp所表示的意義我沒看懂！！！跪求大佬們解釋一波！！！

    def stoneGame(self, p):

        n = len(p)

        dp = p[:]

        for d in range(1, n):

            for i in range(n - d):

                dp[i] = max(p[i] - dp[i + 1], p[i + d] - dp[i])

        return dp[0] > 0

conclusion: discuss中個個都是人才。。