歡迎轉載,但請註明出處並附帶鏈接
算法好久沒複習了,今天看見一妹子在辦公室同時在刷leetcode,頓時我也來了興趣,也準備刷着玩。仔細想想以前學算法時,或多或少都有些遺漏或不足,藉著這次機會都補上。
先從動態規劃下手吧,記得當初在這個算法上掙扎了很久。本文先理論后實踐

動態規劃(DP)

該算法的核心價值就兩部分:描述狀態推導狀態的演變過程。其餘基礎概念我不介紹了,網上大牛寫的好文多得是。在這就說說自己的感受。
這個核心價值可以解決很多的DP問題,感覺更像是一種泛式( 這裏想表達:這是一個一般性的解決方案,如果具體到某一個問題上,都有改進的空間)。很多東西學到最後都是一種思想,只是在某一具體問題上表現形式不同。
到這理論結束,下面來實戰,就圍繞這個核心價值轉

  • 例1 LeetCode 198. House Robber
    根據之前所講,只要找到描述狀態推導狀態演變過程就能解決該問題,那麼住這裏描述狀態是什麼呢? 這裏其實很簡單,只有一種狀態(本人採用數組來記錄),因為根據題目的description只需記錄搶到當前屋子的最大值就ok,描述狀態如下:
    res[i]:搶到第 i個屋子時的目前利益最大值
    下面就要找推導狀態的演變過程。演變過程用文字描述起來太累也不清晰,採用數學公式來說明,如下(圖片是自己做的,找個了在線公式編輯器):

CodeCogsEqn.gif

當i=0時,只有一個房子,為了最大值,怎麼可能不搶
當i=1時,就要比較下哪個屋子更值錢,然後再搶
當i>=2時,就要根據題目要求進行下判斷了,分為不搶,其中 f(i-1) 就代表不搶,所以最大利益和上一項相同,而另一個就代表搶。在不搶中找出最大值

代碼如下(python實現):

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        # create the statement
        res = []
        res = range( len(nums) )
        # i = 0
        res[0] = nums[0]
        # i = 1
        if len(nums) > 1: res[1] = max( nums[0], nums[1] )
        # i >= 2
        for i in range( 2, len(nums) ):
            res[i] = max( res[i-1], res[i-2] + nums[i] )

        return res[-1]

上面代碼還有改進空間,正如本人之前說的”這是一個一般性的解決方案,如果具體到某一個問題上,都有改進的空間”

  • 例2 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown
    來,先找描述狀態,從題目中能發現3個狀態(本人用3個數組來記錄),如下:
    buy[i]: 截至到第 i 天的最大值,且第 i 天執行的是buy操作
    sell[i]: 截至到第 i 天的最大值,且第 i 天執行的是sell操作
    rest[i]: 截至到第 i 天的最大值,且第 i 天執行的是rest操作
    下一步就是 推導狀態的演變過程。根據題目的邏輯很輕鬆就能用如下3個演變過程:
    設price為第i 天的價格

    // buy操作的第i天只有兩種可能(**買**和**不買**)
    // 不買就是buy[i-1];買就必須從rest[i-1]狀態切換過來,還要再減去當天的價格
    buy[i] = max( rest[i-1] - price, buy[i-1] )
    // sell操作也是兩種可能(**賣**和**不賣**)
    // 不賣就是sell[i-1], 賣就從buy[i-1]的狀態切換過來,再加上當天價格
    sell[i] = max( buy[i-1] + price, sell[i-1] )
    // 這個演變過程被簡化過了
    // 其原型是max(sell[i-1], buy[i-1], rest[i-1]), 因為rest操作什麼也不做,所以就從3個狀態中找最大值
    // 但是根據題意,不能出現{buy, rest, buy}這種不合理得排序,就刪除了buy[i-1]
    rest[i] = max( sell[i-1], rest[i-1] )

    python代碼如下:
    注意初始化buy[0]和sell[0],也挺簡單的,就不詳述了

    class Solution(object):
      def maxProfit(self, prices):
          """
          :type prices: List[int]
          :rtype: int
          """
          if len(prices) < 2: return 0
    
          buy = [ 0 for _ in range( len(prices) )]
          sell = [ 0 for _ in range( len(prices) )]
          rest = [ 0 for _ in range( len(prices) )]
    
          buy[0] = -prices[0] # After buy, you should have -prices[0] profit. Be positive!
          sell[0] = -sys.maxint - 1 # you can sell before buy, set sell to MIN
    
          for i in range( 1, len(prices) ):
              buy[i] = max(rest[i-1]-prices[i], buy[i-1])
              sell[i] = max(buy[i-1]+prices[i], sell[i-1])
              rest[i] = max(sell[i-1], rest[i-1])
    
          return max( sell[-1], rest[-1] )

5/25/2017 更新

  • 例3 LeetCode 486. Predict the Winner
    這次描述狀態並不是那麼直接,分析一下得到如下:
    dp(i,j):累加 player1從第 i 個位置到第 j 個位置選擇的數值(即每次選值之和),請注意這個累加值並不是整個數組每項疊加,而是根據題意得出來的(player1選擇一個,player2再選擇一個,一直重複下去。然後將player1每次選值相加得到dp(i,j) )
    其中用一個二維數組表示dp(i,j),即dp[ i ][ j ]。看待dp[i][j]時,不要把它想成一個下標表示的值,而是把它看成從 i 到 j 的按題意邏輯得到的累加值,這樣比較好理解下面的代碼,這點很重要!!!
    在用數學公式表達下:
    dp(i,j) = max( sum(i,j-1) - dp(i,j-1) + nums[j], 
                   sum(i+1,j) - dp(i+1,j) + nums[i] )

    簡化后,得到:

    dp(i,j) = max( sum(i,j) - dp(i,j-1) , sum(i,j) - dp(i+1,j) )

    下面找推導狀態的演變過程,其實上面那個式子就可以說是演變過程,但對於解題來說很不理想,所以這次從題目分析。
    題目想問player1能不能贏,也就是問player1最後的數值是不是大於player2的數值,即player1 – player2 > 0
    下面進行一些數學推導(字跡不好看,請注意看思路:-) ):


公式推導.JPG

到此描述狀態推到演變過程都結束了
下面開始上代碼(依舊python,代碼之後還有對一些迷茫地方的講解):

class Solution(object):
    def PredictTheWinner(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """       
        # store the maximum score player1 picking from i to j
        dp = [ [0 for _ in range(len(nums))] for _ in range(len(nums))]

        # initializing
        for i in range( len(nums) ): dp[i][i] = nums[i]

        for i in range( 1, len(nums) ):
            for j in range( 0, len(nums)-i ):
                dp[j][j+i] = max( nums[j+i] - dp[j][j+i-1], nums[j] - dp[j+1][j+i] )

        return dp[0][-1] >= 0
  1. 可能有人會問“初始化那一行在做什麼?”。首先,在任何dp問題中,我們都需要初始化某些值(就是那種能從題目中得到的確定值,在動態規劃開始之前它們就已經存在了),在這道題目中能確定的只有dp[0][0] = nums[0], dp[1][1] = nums[1], dp[2][2] = nums[2]…等等。dp[0][0]就是開頭說的dp(0,0),即從第0個開始到第0個結束所能得到的累加值,這裏只有nums[0]這一個值,後面幾個dp[1][1],dp[2][2]同理
  2. 還有人可能問那個雙重循環在干什麼?。我們要把全部的case列舉出來,放張圖舉個例子(長度為6的數組):

舉例(1).JPG

今天就說到這了

以後會接着更!!!