1.part1 緒論 計(jì)算機(jī)是有限狀態(tài)機(jī)

計(jì)算機(jī)本質(zhì)上是一臺(tái)有限狀態(tài)機(jī)全封，只能根據(jù)已經(jīng)計(jì)算過(guò)的狀態(tài)集合（calculated state set）频鉴，利用狀態(tài)轉(zhuǎn)移函數(shù)（state transfer function）缺厉，來(lái)計(jì)算下一個(gè)狀態(tài)（next state）

動(dòng)態(tài)規(guī)劃就是如此永高，利用已經(jīng)計(jì)算過(guò)的狀態(tài)和狀態(tài)轉(zhuǎn)移方程隧土，來(lái)求解目標(biāo)狀態(tài)的值

這里要討論的是一類問(wèn)題，我將這類問(wèn)題叫做行為狀態(tài)樹(shù)（行為狀態(tài)圖更恰當(dāng)）問(wèn)題（個(gè)人定義乏梁，方便自己理解）如圖：

行為狀態(tài)樹(shù)

對(duì)于行為狀態(tài)圖問(wèn)題亥啦，我們總是不能一步到位地得出問(wèn)題當(dāng)前階段的目標(biāo)狀態(tài)的通項(xiàng)公式，看起來(lái)只能遍歷所有的情況练链，也就是窮舉來(lái)尋求目標(biāo)解了

但是翔脱，如果當(dāng)前狀態(tài)和之前的若干個(gè)更小的狀態(tài)可以建立起【遞推關(guān)系】，而我們又把問(wèn)題的每一個(gè)中間狀態(tài)都記錄下來(lái)媒鼓，這樣届吁，求解當(dāng)前狀態(tài)的值就轉(zhuǎn)化成了求解之前的若干個(gè)更小狀態(tài)的值，自頂向下的遞歸 或者 自底向上的遞推绿鸣，都可以輕松解決疚沐。因此，【找到問(wèn)題與子問(wèn)題之間的狀態(tài)遞推式是關(guān)鍵】

2.part2 動(dòng)態(tài)規(guī)劃的內(nèi)涵和特征

• 什么是最優(yōu)子結(jié)構(gòu)

問(wèn)題分解成若干個(gè)子問(wèn)題后潮模，可以通過(guò)【子問(wèn)題的最優(yōu)解】亮蛔，推導(dǎo)出問(wèn)題的最優(yōu)解。也就是擎厢，最優(yōu)解必須可以由之前的最優(yōu)解推出

• 什么是重疊子問(wèn)題

注意究流，不要將重疊子問(wèn)題等同于相等子問(wèn)題。重疊子問(wèn)題是指涉及的計(jì)算有部分重疊或者完全重疊的子問(wèn)題动遭，如子問(wèn)題A計(jì)算自然數(shù)1到5的和芬探，子問(wèn)題B計(jì)算自然數(shù)0到6的和，那么AB就是存在計(jì)算重疊（部分重疊）的
那么厘惦，因?yàn)榇嬖谥丿B的子問(wèn)題偷仿，動(dòng)態(tài)規(guī)劃對(duì)每個(gè)子問(wèn)題只解決一次，然后將解存儲(chǔ)起來(lái)（字典绵估、數(shù)組或者單變量炎疆，視具體問(wèn)題而定），等下次需要這個(gè)子問(wèn)題的解時(shí)国裳，直接取出即可形入，不需反復(fù)計(jì)算。另外缝左，當(dāng)存在重疊子問(wèn)題時(shí)亿遂，就一定滿足最優(yōu)子結(jié)構(gòu)性質(zhì)

• 什么是無(wú)后效性（without aftereffect）

通俗地理解就是浓若，“未來(lái)與過(guò)去無(wú)關(guān)，只和現(xiàn)在有關(guān)∩呤現(xiàn)在屏蔽了過(guò)去挪钓，一切從現(xiàn)在出發(fā)”。某階段的狀態(tài)一旦確定耳舅，此后過(guò)程的演變則不再關(guān)心此前各階段的狀態(tài)及決策碌上，只關(guān)心當(dāng)前的狀態(tài)是怎樣的。例如我們的人生就是無(wú)后效性的浦徊，我們大學(xué)畢業(yè)找什么樣的工作馏予，只關(guān)心我們畢業(yè)時(shí)的學(xué)校文憑、知識(shí)水平等盔性，并不關(guān)心我們之前到底上了什么小學(xué)霞丧、初中、高中

現(xiàn)在看一下動(dòng)態(tài)規(guī)劃是什么東東

先記住冕香，A.動(dòng)態(tài)規(guī)劃的目的蛹尝，是為了求最優(yōu)解，即求最值悉尾，B.當(dāng)前問(wèn)題和子問(wèn)題通過(guò)狀態(tài)轉(zhuǎn)移方程形成圖結(jié)構(gòu)

動(dòng)態(tài)規(guī)劃（Dynamic programming突那，DP）

• 動(dòng)態(tài)規(guī)劃核心是窮舉，但它的窮舉有點(diǎn)特別焕襟，因?yàn)檫@類問(wèn)題存在「重疊子問(wèn)題」陨收，暴力窮舉產(chǎn)生了大量的重復(fù)計(jì)算饭豹，效率極其低下鸵赖，需要「?jìng)渫洝够蛘摺窪P table」來(lái)優(yōu)化窮舉過(guò)程，避免重復(fù)計(jì)算拄衰。
• 而且它褪，動(dòng)態(tài)規(guī)劃問(wèn)題一定會(huì)具備「最優(yōu)子結(jié)構(gòu)」，才能通過(guò)子問(wèn)題的最值得到原問(wèn)題的最值
  • （敲黑板翘悉，重點(diǎn)）
    通過(guò)建立當(dāng)前問(wèn)題與之前規(guī)模更小的若干個(gè)問(wèn)題間的【遞推式】（注意：動(dòng)態(tài)規(guī)劃的遞推式可以是跳躍式的茫打，也可以是相鄰問(wèn)題規(guī)模間的遞推），將求解問(wèn)題轉(zhuǎn)化為求解若干個(gè)子問(wèn)題妖混，直到子問(wèn)題的解已知（即遞歸出口）老赤；并且這一系列子問(wèn)題會(huì)存在重疊，我們對(duì)子問(wèn)題首次計(jì)算后制市，將對(duì)應(yīng)的解保存起來(lái)抬旺，避免下次又進(jìn)行重復(fù)計(jì)算

3.part3 動(dòng)態(tài)規(guī)劃的兩種寫法：

• A.到哪里去（迭代法、自底向上法祥楣、狀態(tài)表法开财、遞增規(guī)模法汉柒。【我個(gè)人喜歡這種寫法，能體現(xiàn)dp的思想】）

#####################################################
1.定義子問(wèn)題要求解什么最XX解责鳍。一般而言碾褂，首先考慮原問(wèn)題求啥，子問(wèn)題就求啥历葛；如果這樣不能建立狀態(tài)轉(zhuǎn)移方程正塌，再考慮原問(wèn)題可以轉(zhuǎn)化為求啥，然后考慮子問(wèn)題恤溶。無(wú)論如何传货，子問(wèn)題必須要求解一個(gè)最XX
2.寫出問(wèn)題與子問(wèn)題間的狀態(tài)轉(zhuǎn)移方程，構(gòu)造dp數(shù)組宏娄。dp數(shù)組的每個(gè)元素對(duì)應(yīng)不同規(guī)模子問(wèn)題的最XX解
3.寫出dp table的base case
4.確定dp table的填空方向
#####################################################

• B.從哪里來(lái)（遞歸法问裕、自頂向下法、狀態(tài)轉(zhuǎn)移方程法孵坚、縮小規(guī)模法）
  從哪里來(lái)粮宛，就是不斷回溯到當(dāng)前問(wèn)題的上一階段，不斷縮小問(wèn)題規(guī)模卖宠，直到達(dá)到起點(diǎn)為止巍杈。這種情況下，考慮的方向就是通過(guò)狀態(tài)轉(zhuǎn)移方程扛伍，以遞歸的方式不斷縮小問(wèn)題規(guī)模
  靈活的是筷畦，問(wèn)題的起始點(diǎn)和結(jié)束點(diǎn)是相對(duì)的，從A到B刺洒，也可以看作從B到A鳖宾，因此可以說(shuō)從A到B去，B從A來(lái)逆航；也可以說(shuō)從B到A去鼎文，A從B來(lái)

4.單狀態(tài)dp問(wèn)題與多狀態(tài)dp問(wèn)題

4.1 單狀態(tài)dp問(wèn)題

單狀態(tài)dp問(wèn)題，指一個(gè)規(guī)模問(wèn)題下只存在一種狀態(tài)因俐，我們只需要關(guān)注這一種狀態(tài)的轉(zhuǎn)移拇惋，就可以求解目的問(wèn)題。如最長(zhǎng)路徑問(wèn)題抹剩、最短路徑問(wèn)題撑帖、最大和問(wèn)題、最小和問(wèn)題澳眷、尋路總數(shù)等這一類簡(jiǎn)單的加法或計(jì)數(shù)問(wèn)題

先看5個(gè)單狀態(tài)的動(dòng)態(tài)規(guī)劃例子
1).【計(jì)算數(shù)字塔從上到下所有路徑中和最大的路徑】
數(shù)字塔是第i行有i個(gè)數(shù)字組成胡嘿，從上往下每個(gè)數(shù)字只能走到他正下方數(shù)字或者右下方數(shù)字，求數(shù)字塔從上到下所有路徑中和最大的路徑境蔼，如有下數(shù)字塔：

3
1 5
8 4 3
2 6 7 9
6 2 3 5 1

最大路徑是3-5-3-9-5灶平，和為25伺通。我們可以分別從自頂向下和自底向上兩種角度去解。以1層為底逢享，5層為頂：

• 自頂向下
  定義max(i, j, n)為第i行第j個(gè)元素到第n層的最大路徑函數(shù)
  value(i, j)為第i行第j個(gè)元素的值
  關(guān)鍵：通過(guò)狀態(tài)轉(zhuǎn)移式縮小問(wèn)題規(guī)模

# 用于存放各子問(wèn)題的最優(yōu)解的全局字典罐监，避免重復(fù)計(jì)算
sub_questions = {}
def max(i,j,n):
    #遞歸出口
    if i == n: 
        return value(i, j)
    k = 'max%s%s%s' % (str(i), str(j), str(n))
    # 如果當(dāng)前子問(wèn)題的解在字典里，直接返回瞒爬；否則求出后放入字典再返回
    if k not in sub_questions:
        # 這是最關(guān)鍵的狀態(tài)轉(zhuǎn)移式弓柱，縮小問(wèn)題規(guī)模
        sub_questions[k] = value(i,j) + max(max(i+1, j, n), max(i+1, j+1, n))
    return sub_questions[k]

因此，所求 = max(1,1,5) = value(1,1) + max(max(2,1 5), max(2,2,5))
然后不斷遞歸侧但，直到進(jìn)入i == n遞歸結(jié)束

• 自底向上（recommended）
  1.定義子問(wèn)題的解矢空。原問(wèn)題求首層到尾層的最大路徑，那么考慮子問(wèn)題也是求首層到某層最大路徑禀横，但這樣難以找到兩者間的關(guān)系屁药；考慮拆分原問(wèn)題，求解原問(wèn)題等于求解max(首層到尾層各個(gè)位置的最大路徑)柏锄，發(fā)現(xiàn)這樣好找遞推關(guān)系酿箭，那么【子問(wèn)題就是求解首層到當(dāng)前位置的最大路徑】
  2.狀態(tài)轉(zhuǎn)移方程。規(guī)劃一張二維狀態(tài)表dp趾娃，dp[i][j]表示首層到第i行第j個(gè)元素的最大路徑缭嫡，則dp[i][j] = value(i+1,j+1) + max(dp[i - 1][j], dp[i - 1][j - 1])
  3.確定base case。dp[0][0] = value(1,1)
  4.確定dp table填寫的方向抬闷。由狀態(tài)轉(zhuǎn)移方程妇蛀，dp table填寫的方向?yàn)閺纳系较拢瑥淖蟮接?/li>

過(guò)程可視化如下：

3                            3                            3                             3

1    5                       4    8                       4    8                        4    8

8    4    3                  8    4    3                  12   12  11                   12   12   11  

2    6    7    9             2    6    7    9             2    6    7    9             14   18   19   20

6    2    3    5    1        6    2    3    5    1        6    2    3    5    1        20   20   22   25   21

# 初始化最大距離
max_route = 0
# 創(chuàng)造并初始化二維狀態(tài)表
dp = [ [0 for j in range(i+1)] for i in range(n)]
dp[0][0] = value(1,1)
for i in range(1, n):
    j = 0
    while j <= i:
        # 如果是第一列笤成，等于自身+上一位置的狀態(tài)值
        if j == 0:
            dp[i][j] = value(i+1,j+1) + dp[i - 1][j]
        # 否則评架，等于自身+（上一位置和左上位置的最大狀態(tài)值）
        else:
            dp[i][j] = value(i+1,j+1) + max(dp[i - 1][j], dp[i - 1][j - 1])
        max_route = max(max, dp[i][j])
        j += 1
return max_route

這里還能使用滾動(dòng)dp數(shù)組優(yōu)化，因?yàn)榈侥承械淖畲缶嚯x只與上一行的dp值有關(guān)

2). 【最大子序和】
給定一個(gè)整數(shù)數(shù)組 nums 疹启，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）古程，返回其最大和

示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大蔼卡，為 6

• 自底向上法 思路：
  對(duì)于這一題喊崖，我們很容易想到暴力窮舉的思路就是從數(shù)組首個(gè)元素到最后一個(gè)元素做一次二維的遍歷，求出所有可能的和雇逞，然后取最大荤懂。那么，哪些計(jì)算是重復(fù)并且可用于遞推的呢塘砸？容易發(fā)現(xiàn)节仿，以nums[i]結(jié)尾的最大子序和 = max(nums[i], 以nums[i-1]結(jié)尾的最大子序和 + nums[i])，而原問(wèn)題的解恰好等價(jià)于以nums[i]結(jié)尾的最大子序和中的最大值（即：將原問(wèn)題分治后掉蔬，得到的各子問(wèn)題間可以遞推）廊宪。注意到矾瘾，上面的斜體部分的值是暴力遍歷中重復(fù)計(jì)算并且可用于遞推的，因此我們用dp table把這些值存起來(lái)就game over了

# 自底向上法
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(nums)
        max_sum = nums[0]
        # dp[i]記錄以nums[i]結(jié)尾的最大子序和
        dp = [0 for i in range(L)]
        dp[0] = nums[0]
        for i in range(1, L):
            # 狀態(tài)轉(zhuǎn)移關(guān)系箭启，注意千萬(wàn)別弄錯(cuò)
            dp[i] = max(dp[i-1] + nums[i], nums[i])
            # 找當(dāng)前的最大和
            max_sum = max(max_sum, dp[i])
        # print(dp)
        return max_sum

后來(lái)看別人的提醒壕翩，發(fā)現(xiàn)每一次遞推其實(shí)只用到上一次的最大子序和，再之前的值都不必保存傅寡，于是修改了一下放妈，將數(shù)組dp存過(guò)往的所有值改成單變量dp_last存放上一個(gè)值，減少空間占用荐操，代碼如下：

# 自底向上法
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(nums)
        max_sum = nums[0]
        # dp_last記錄遞推中的上一個(gè)最大子序和
        dp_last = nums[0]        
        for i in range(1, L):
            # 狀態(tài)轉(zhuǎn)移關(guān)系
            dp_now = max(dp_last + nums[i], nums[i])
            # 找當(dāng)前的最大和
            max_sum = max(max_sum, dp_now)
            dp_last = dp_now
        return max_sum

• 自頂向下
  自頂向下的方法其實(shí)就是自底向上的逆方法芜抒，使用遞歸調(diào)用來(lái)實(shí)現(xiàn)。
  本題先將原問(wèn)題分成了N個(gè)子問(wèn)題托启，N為傳入的數(shù)組的長(zhǎng)度宅倒，每個(gè)子問(wèn)題是求以nums[i]結(jié)尾的最大序和，這時(shí)原問(wèn)題就等價(jià)于求max(N個(gè) 以nums[i]結(jié)尾的最大序和)屯耸。我們發(fā)現(xiàn)唉堪，這N個(gè)子問(wèn)題之間是存在遞推關(guān)系的！＜缑瘛唠亚！，所以原問(wèn)題等價(jià)于保存遞歸中間過(guò)程值的持痰、求以數(shù)組最后一個(gè)元素結(jié)尾的最大序和的問(wèn)題
  那么灶搜，容易想到，原問(wèn)題的最優(yōu)解可能在等價(jià)問(wèn)題的遞歸中間過(guò)程出現(xiàn)工窍，這里需要記錄遞歸過(guò)程中產(chǎn)生的所有中間值割卖，然后從這些中間值中尋找滿足題意的最優(yōu)解

max_sum = 0
# 求以nums數(shù)組最后一個(gè)元素結(jié)尾的最大序和
def maxendwith_nums_last_element(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    L = len(nums)
    global max_sum
    # 遞歸出口
    if L == 1:
        max_endwith_nums_last_element = nums[0]
        # 修改最大和
        max_sum = max(max_endwith_nums_last_element, max_sum)
        # 返回以數(shù)組最后一個(gè)元素結(jié)尾的序列最大和
        return max_endwith_nums_last_element
    # 狀態(tài)轉(zhuǎn)移式，縮小問(wèn)題規(guī)模患雏，不斷遞歸
    max_endwith_nums_last_element = max(maxSubArray(nums[:-1]) + nums[-1], nums[-1])
    max_sum = max(max_endwith_nums_last_element, max_sum)
    # 返回以數(shù)組最后一個(gè)元素結(jié)尾的序列最大和
    return max_endwith_nums_last_element

def getMaxSum(nums):
    global max_sum
    maxendwith_nums_last_element(nums)
    return max_sum
        
print(getMaxSum([-2,1,-3,4,-1,2,1,-5,4]))
>>> 6

3). 爬n 階樓梯鹏溯，每次可以爬 1 或 2 個(gè)臺(tái)階，求共有多少種不同的方法
輸入： n 正整數(shù)
輸出：method_count 正整數(shù)
如：
輸入：2
輸出：2
因?yàn)橛袃煞N方法
1】 1 + 1
2】 直接2

這題比較簡(jiǎn)單淹仑，直接寫出自頂向下遞歸的初始代碼：

# 自上而下遞歸丙挽，未保存遞歸過(guò)程中的重復(fù)值
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n > 0:
            if n == 2:
                return 2
            elif n == 1:
                return 1
            else:
                # 遞歸關(guān)系，將當(dāng)前規(guī)模n與子規(guī)模n-1, n-2聯(lián)系在一起匀借，從而不斷縮小問(wèn)題規(guī)模
                return self.climbStairs(n-1) + self.climbStairs(n-2)
        else:
            print('階梯數(shù)必須為正')

以上代碼提交后颜阐，當(dāng)輸入n = 38時(shí)，會(huì)出現(xiàn)超出時(shí)間限制的問(wèn)題吓肋，因?yàn)槲覀冊(cè)谶f歸過(guò)程中凳怨，對(duì)很多子問(wèn)題進(jìn)行了重復(fù)計(jì)算。由于遞歸樹(shù)的結(jié)構(gòu)特性，耗費(fèi)的時(shí)間和空間會(huì)隨著問(wèn)題規(guī)模的增長(zhǎng)指數(shù)級(jí)地增長(zhǎng)

使用全局變量將遞歸過(guò)程中重復(fù)的值存起來(lái)肤舞，供各個(gè)遞歸時(shí)使用紫新。優(yōu)化代碼如下：

# 自上而下遞歸，使用全局變量method_count字典保存遞歸過(guò)程中所有子問(wèn)題的值
method_count = {}
class Solution(object):    
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        global method_count
        if n > 0:
            # 總是先判斷要獲取的值是否已經(jīng)被計(jì)算保存李剖，沒(méi)有則計(jì)算并保存
            if str(n) not in method_count:
                if n == 2:
                    method_count[str(n)] = 2
                elif n == 1:
                    method_count[str(n)] = 1
                else:
                    count = self.climbStairs(n-1) + self.climbStairs(n-2)
                    method_count[str(n)] = count
            return method_count[str(n)]
                
        else:
            print('階梯數(shù)必須為正')

自底向上的也很好寫弊琴，并且只需要保留2個(gè)變量存儲(chǔ)中間值，理論上應(yīng)該減少了空間消耗：

# 自底向上遞推杖爽，每次只保留和更新2個(gè)值a敲董、b
class Solution(object):    
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a = 1
        b = 2
        if n == 1:
            return a
        if n > 2:
            for i in range(2, n):
                b, a = a + b, b
        return b

• 4). 爬蟲(chóng)位于一個(gè) m x n 網(wǎng)格的左上角第一個(gè)網(wǎng)格內(nèi)，m 為列數(shù)慰安，n為行數(shù)腋寨。爬蟲(chóng)每次只能向下或者向右移動(dòng)一步，則達(dá)到網(wǎng)格的右下角最后一個(gè)網(wǎng)格共有多少條不同的路徑化焕？
  直接貼代碼吧萄窜，寫了這么多字也有感覺(jué)了

# 爬蟲(chóng)位于一個(gè) m x n 網(wǎng)格的左上角第一個(gè)網(wǎng)格內(nèi)，m 為列數(shù)撒桨，n為行數(shù)查刻。
# 爬蟲(chóng)每次只能向下或者向右移動(dòng)一步，則達(dá)到網(wǎng)格的右下角最后一個(gè)網(wǎng)格共有多少條不同的路徑凤类？


# 法一 利用排列組合知識(shí)解答
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        total_step = m+n-2
        a = 1
        for i in range(m, total_step+1):
            a = a*i
        b = 1
        for i in range(1, n):
            b = b*i
        return a/b


# 法二 自頂向下的動(dòng)態(tài)規(guī)劃
dict_value = {}
class Solution(object):    
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        global dict_value
        # 當(dāng)只能向下或者向右時(shí)穗泵，只有一條路可以走
        if m == 1 or n == 1:
            return 1
        # 其余的情況下，先查字典看看當(dāng)前問(wèn)題有沒(méi)有被計(jì)算后存儲(chǔ)下來(lái)谜疤，無(wú)則計(jì)算后存入字典
        if "%s %s" % (m, n) not in dict_value:
            # 遞歸關(guān)系
            dict_value["%s %s" % (m, n)] = self.uniquePaths(m, n-1) + self.uniquePaths(m-1, n)
        return dict_value["%s %s" % (m, n)]


# 法三 自底向上的動(dòng)態(tài)規(guī)劃佃延，這里通過(guò)dp狀態(tài)表實(shí)現(xiàn)。
# 注意夷磕，通過(guò)狀態(tài)表的話履肃，每一個(gè)狀態(tài)都相互不重復(fù)，每一個(gè)狀態(tài)都要保存坐桩，所以相當(dāng)于自底向上窮舉了
class Solution(object):    
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 創(chuàng)建狀態(tài)表
        dp = [[0 for i in range(m)] for j in range(n)]
        # 初始化起始狀態(tài)尺棋，到達(dá)第一排或第一列的任意點(diǎn)都只有一種走法
        # 初始化第一行
        dp[0] = [1 for i in range(m)]
        # 初始化第一列
        for i in range(n):
            dp[i][0] = 1
        # print(dp)
        if m > 1 and n > 1:
            # 利用遞推關(guān)系，逐步填寫狀態(tài)表
            for i in range(1, n):
                for j in range(1, m):
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n-1][m-1]

• 5). 整數(shù)拆分绵跷。將一個(gè)整數(shù)拆分為多個(gè)(至少)整數(shù)膘螟，使拆分后的整數(shù)之積最大
  思路：看到【大整數(shù)拆成小整數(shù)】，大整數(shù)到小整數(shù)抖坪，這就是狀態(tài)轉(zhuǎn)移方程的味道

# 維護(hù)一個(gè)一維dp數(shù)組萍鲸，dp[i]表示整數(shù)i拆分后積的最大值。通過(guò)dp[i] = max( [max(dp[j], j) * max(dp[i-j], i-j)] )進(jìn)行狀態(tài)轉(zhuǎn)移
class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0 for i in range(n+1)]
        # 初始化dp數(shù)組
        dp[1] = 1
        dp[2] = 1
        for i in range(3, n+1):
            ## 狀態(tài)轉(zhuǎn)移方程 ##
            possible_ans = [max(dp[j], j)*max(dp[i-j], i-j) for j in range(1,i//2+1)]
            dp[i] = max(possible_ans)
            ## 狀態(tài)轉(zhuǎn)移方程 ##
        return dp[n]
        

此外擦俐，本題還可通過(guò)數(shù)學(xué)方法求解。設(shè)整數(shù) a = n*x握侧，那么b = x^n = x^(a/x) = (x^(1/x))a蚯瞧，而x^(1/x)的極限為e約為2.718嘿期，因此應(yīng)該盡可能拆分成整數(shù)3，拆不了3再拆成2

另外還有兩道經(jīng)典的動(dòng)規(guī)問(wèn)題埋合，在這里

再加一道題
leetcode221 最大正方形
在一個(gè)由 0 和 1 組成的二維矩陣內(nèi)备徐，找到只包含 1 的最大正方形，并返回其面積甚颂。
例如：

輸入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

輸出: 4

思路：
當(dāng)我們判斷以某個(gè)點(diǎn)為正方形右下角時(shí)最大的正方形時(shí)蜜猾，那它的上方，左方和左上方三個(gè)點(diǎn)也一定是某個(gè)正方形的右下角振诬，否則該點(diǎn)為右下角的正方形最大就是它自己了蹭睡。這是定性的判斷，那具體的最大正方形邊長(zhǎng)呢赶么？

我們知道肩豁，該點(diǎn)為右下角的正方形的最大邊長(zhǎng)，最多比它的上方辫呻，左方和左上方為右下角的正方形的邊長(zhǎng)多1清钥，最好的情況是是它的上方，左方和左上方為右下角的正方形的大小都一樣的放闺，這樣加上該點(diǎn)就可以構(gòu)成一個(gè)更大的正方形祟昭。 但如果它的上方署隘，左方和左上方為右下角的正方形的大小不一樣采幌，合起來(lái)就會(huì)缺了某個(gè)角落嘴秸，這時(shí)候只能取那三個(gè)正方形中最小的正方形的邊長(zhǎng)加1了燕酷。假設(shè)dpi表示以i,j為右下角的正方形的最大邊長(zhǎng)廓旬，則有 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1當(dāng)然排监，如果這個(gè)點(diǎn)在原矩陣中本身就是0的話可岂，那dp[i]肯定就是0了

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        # 可以維護(hù)一個(gè)dp二維數(shù)組陡蝇，dp[i][j]表示matrix[i][j]為正方形右下角的最大正方形的邊長(zhǎng)
        # 這里進(jìn)行了一些優(yōu)化旗吁，選擇原地修改matrix數(shù)組替代dp數(shù)組
        m = len(matrix)
        n = len(matrix[0])
        res = 0
        for i in range(m):
            for j in range(n):
                matrix[i][j] = int(matrix[i][j])
                if matrix[i][j] == 1:
                    res = 1

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] != 0:
                    matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1
                    res = max(res, matrix[i][j])
        return res**2

4.2.多狀態(tài)dp問(wèn)題

多狀態(tài)dp問(wèn)題踩萎，指一個(gè)規(guī)模問(wèn)題下存在多種狀態(tài)，我們需要聯(lián)合關(guān)注多種狀態(tài)間的相互轉(zhuǎn)移很钓，才可以求解目的問(wèn)題香府。經(jīng)典的多狀態(tài)dp問(wèn)題是leetcode 309 最佳買賣股票時(shí)機(jī)含冷凍期，每一天都有3種狀態(tài)：買入码倦，賣出企孩，不持有股票空等-冷凍，第i天這3種狀態(tài)下的最大利潤(rùn)袁稽，都需要依賴第i-1天的這3種狀態(tài)來(lái)推導(dǎo)

leetcode#### 152. 乘積最大子數(shù)組
給一個(gè)整數(shù)數(shù)組 nums 勿璃，找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個(gè)數(shù)字，正負(fù)數(shù)和0都可能出現(xiàn)），返回該子數(shù)組所對(duì)應(yīng)的乘積
解法1：
由于求的是乘積补疑，因此我們應(yīng)該在保證相乘的數(shù)中負(fù)數(shù)的個(gè)數(shù)為偶數(shù)個(gè)的前提下歧沪，盡可能地多相乘非0數(shù)。因此莲组，數(shù)組中的0實(shí)際上把數(shù)組進(jìn)行了分割诊胞，對(duì)于被分割出來(lái)的每一段（只含非0數(shù)），都在保證相乘的數(shù)中負(fù)數(shù)的個(gè)數(shù)為偶數(shù)個(gè)的前提下锹杈，盡可能地多相乘撵孤。
當(dāng)一個(gè)數(shù)組中沒(méi)有0存在，則分為兩種情況：
1.負(fù)數(shù)為偶數(shù)個(gè)竭望，則整個(gè)數(shù)組的各個(gè)值相乘為最大值邪码；
2.負(fù)數(shù)為奇數(shù)個(gè)，則從左邊開(kāi)始市框，乘到最后一個(gè)負(fù)數(shù)停止有一個(gè)“最大值”霞扬，從右邊也有一個(gè)“最大值”，比較枫振，得出最大值喻圃。
取所有乘積中最大的一個(gè)

代碼怎么實(shí)現(xiàn)呢？先計(jì)算從左到右的相乘的最大值粪滤，碰到0置0斧拍；再計(jì)算從右到左的最大值，碰到0置0杖小；再將兩組最大值相比肆汹。妙啊Ｓ枞ā昂勉！

class Solution:
    def maxProduct(self, A):
        B = A[::-1]
        for i in range(1, len(A)):
            A[i] *= A[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(max(A),max(B))

動(dòng)態(tài)規(guī)劃思路：
搞一個(gè)一維dp數(shù)組，dp[i]需要記錄【兩個(gè)值】扫腺，或者說(shuō)記錄【兩個(gè)狀態(tài)】岗照，一個(gè)為以nums[i]結(jié)尾的子數(shù)組的最大值，一個(gè)為以nums[i]結(jié)尾的子數(shù)組的最小值笆环。為啥攒至？因?yàn)閿?shù)組里有負(fù)數(shù)存在，如果nums[i+1]是正數(shù)躁劣，那么它需要以nums[i]結(jié)尾的子數(shù)組的最大值迫吐；如果nums[i+1]是負(fù)數(shù)，那么它需要以nums[i]結(jié)尾的子數(shù)組的最小值

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # dp數(shù)組, dp[i]包含2個(gè)值账忘，以nums[i]結(jié)尾的子數(shù)組的乘積的最大值和最小值
        dp = [[] for i in range(len(nums))]
        # 初始化dp
        dp[0] = [nums[0],nums[0]]
        ans = float('-inf')
        ans = max(nums[0], ans)
        for i in range(1, len(nums)):
            # 狀態(tài)轉(zhuǎn)移方程
            max_multi = max(dp[i-1][0]*nums[i], dp[i-1][1]*nums[i], nums[i])
            min_multi = min(dp[i-1][0]*nums[i], dp[i-1][1]*nums[i], nums[i])
            # 狀態(tài)轉(zhuǎn)移方程
            dp[i] = [max_multi, min_multi]
            ans = max(max_multi, ans)
        return ans

多狀態(tài)dp問(wèn)題下志膀，dp table需要保持多個(gè)狀態(tài)熙宇。更本質(zhì)地說(shuō)，有多少個(gè)狀態(tài)梧却，就需要維護(hù)多少個(gè)dp table

leetcode 309. 最佳買賣股票時(shí)機(jī)含冷凍期
給定一個(gè)整數(shù)數(shù)組奇颠，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 败去。?
設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)放航。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）圆裕。
賣出股票后广鳍，你無(wú)法在第二天買入股票 (即冷凍期為 1 天)。
這也是一道多狀態(tài)dp問(wèn)題吓妆。多狀態(tài)dp問(wèn)題可以使用一個(gè)dp數(shù)組赊时，每個(gè)存儲(chǔ)單元存儲(chǔ)多個(gè)狀態(tài)；亦可以使用多個(gè)相互關(guān)聯(lián)的dp數(shù)組行拢，每個(gè)數(shù)組的存儲(chǔ)單元存儲(chǔ)各自負(fù)責(zé)的狀態(tài)祖秒。本題就使用了3個(gè)關(guān)聯(lián)的dp數(shù)組，相對(duì)更加直觀

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        # 每一天都有3種狀態(tài)舟奠，買/賣/不操作竭缝，分別用buy/sell/freeze數(shù)組標(biāo)記
        # buy[i]表示在第i天進(jìn)行買入后的最大總收益
        # sell[i]表示在第i天進(jìn)行賣出后的最大總收益
        # freeze[i]表示在第i天混吃等死的最大總收益

        # 1.首先顯然有freeze[i] = max(buy[i-1], sell[i-1], freeze[i-1])的關(guān)系式，即【今天混吃等死的收益 = max(昨天混吃等死收益沼瘫，昨天買入收益抬纸，昨天賣出收益)】
        # 這里可以優(yōu)化一下，因?yàn)閎uy[i-1]永遠(yuǎn)小于freeze[i-1]耿戚。為啥湿故？因?yàn)椴还芮懊鎺滋煸趺礃樱菇刂廉?dāng)前收益最大膜蛔，肯定今天不能再花錢去買了坛猪，啥都不干就沒(méi)有支出，手里的錢肯定更多
        # 所以皂股，freeze[i] = max(sell[i-1], freeze[i-1])

        # 2.然后墅茉，sell[i]也可以很自然地推出，sell[i] = prices[i] + max(buy[:i])
        # 3.最后是buy[i]屑墨，根據(jù)冷凍期設(shè)定躁锁，buy[i] = freeze[i-1] - prices[i]

        l = len(prices)
        if l <= 1:
            return 0
        
        buy = [0 for i in range(l)]
        sell = [0 for i in range(l)]
        freeze = [0 for i in range(l)]
        buy[0] = - prices[0]
        for i in range(1, l):
            buy[i] = freeze[i-1] - prices[i]
            sell[i] = prices[i] + max(buy[:i])
            freeze[i] = max(sell[i-1], freeze[i-1])
        return max(sell[-1], freeze[-1])

另一種dp寫法：
上面的dp table中，以buy為例卵史，buy[i]表示在第i天進(jìn)行買入后的最大總收益战转，這里換一種定義方式，buy[i]表示截至第i天時(shí)買入為最后狀態(tài)下所對(duì)應(yīng)的最大總收益以躯，同理有sell[i]和freeze[i]
賦予dp的定義不同槐秧，狀態(tài)轉(zhuǎn)移方程也就不同啄踊。于是，新的dp代碼如下刁标。注意颠通，由于sell[i] = max(sell[i-1], prices[i] + buy[i-1])，相比上面求sell[i]的O(n)時(shí)間復(fù)雜度膀懈，這里做到了O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        # xxx[i]表示到第i天為止的最后一個(gè)動(dòng)作是xxx時(shí)的最大利潤(rùn)顿锰，【買入，賣出启搂，不持有光等待-凍結(jié)】
        buy, sell, freeze = [[0 for _ in range(n)] for i in range(3)]
        buy[0] = -prices[0]
        for i in range(1, n):
            buy[i] = max(buy[i-1], freeze[i-1] - prices[i])
            sell[i] = max(sell[i-1], prices[i] + buy[i-1])
            freeze[i] = max(freeze[i-1], sell[i-1])    
        # print(buy, freeze, sell)
        return max(sell[-1], freeze[-1])

LCP 19. 秋葉收藏集

給定一個(gè)僅包含r和y的字符串硼控，要求整體形成ryr的3部分，即左邊是連續(xù)的r胳赌，中間是連續(xù)的y牢撼，右邊是連續(xù)的r，每一部分長(zhǎng)度都>= 1疑苫。每次操作都可以將任意一個(gè)r變成y熏版，也可以將y變成r。求形成ryr結(jié)構(gòu)最少需要操作多少次

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        n = len(leaves)
        #  
        #     dp table, f[i][j]中：
        #         i表示終止下標(biāo)
        #         j表示3種狀態(tài)：0-i位置屬于左半邊右端點(diǎn)捍掺，1-i位置為中間部分右端點(diǎn)撼短，2-i為右半邊右端點(diǎn)
        #     f[i][j] 表示 從0到i需要調(diào)整的葉子數(shù)
        #  
        f = [[0, 0, 0] for _ in range(n)]
        f[0][0] = int(leaves[0] == "y")
        # 第0個(gè)位置不可能是【中間部分或右半邊】的右端點(diǎn)，第1個(gè)位置不可能是右半邊的右端點(diǎn)乡小，置為無(wú)窮大
        f[0][1] = f[0][2] = f[1][2] = float("inf")

        for i in range(1, n):
            isRed = int(leaves[i] == "r")
            isYellow = int(leaves[i] == "y")
            f[i][0] = f[i - 1][0] + isYellow
            f[i][1] = min(f[i - 1][0], f[i - 1][1]) + isRed
            if i >= 2:
                f[i][2] = min(f[i - 1][1], f[i - 1][2]) + isYellow
        
        return f[n - 1][2]

part4 我對(duì)動(dòng)態(tài)規(guī)劃與貪心算法的對(duì)比理解

動(dòng)態(tài)規(guī)劃阔加，本質(zhì)上是 【滿足最優(yōu)子結(jié)構(gòu)和無(wú)后效性的問(wèn)題】的 【優(yōu)化的窮舉法】

貪心算法，本質(zhì)上是“貪心”思想指導(dǎo)下的【定式規(guī)劃】满钟，或者說(shuō)【定式?jīng)Q策】

• 傳統(tǒng)的窮舉法胜榔，一般都是brute force暴力計(jì)算所有情況下的目標(biāo)值，而不考慮計(jì)算過(guò)程中是否存在某些值被重復(fù)計(jì)算的問(wèn)題

• 貪心算法并非動(dòng)態(tài)規(guī)劃湃番，反而是“固態(tài)規(guī)劃”夭织。貪心與動(dòng)規(guī)都需要滿足最優(yōu)子結(jié)構(gòu)和無(wú)后效性，有些資料會(huì)由此認(rèn)為貪心算法是一種特殊的動(dòng)態(tài)規(guī)劃吠撮，我認(rèn)為不然尊惰。理由如下：
  動(dòng)態(tài)規(guī)劃是優(yōu)化過(guò)的窮舉，本質(zhì)上還是窮舉泥兰，需要考慮所有子問(wèn)題的最優(yōu)解才能得到最終的最優(yōu)解弄屡，然后將最優(yōu)解作為決策的依據(jù)；
  但貪心算法并不是窮舉鞋诗，它固定地考慮每一階段到下一階段的最優(yōu)作為決策的依據(jù)膀捷，是“貪心”的定式，不是一個(gè)動(dòng)態(tài)求最優(yōu)解的過(guò)程削彬。另外全庸，貪心算法得到的是局部最優(yōu)解

part5 貪心算法的應(yīng)用

既然貪婪算法只能得到局部最優(yōu)秀仲，那么它能發(fā)揮什么作用呢？---動(dòng)態(tài)規(guī)劃的替代品

貪婪算法(近似算法)在大部分情況下易于實(shí)現(xiàn)壶笼，效率高神僵。當(dāng)問(wèn)題的規(guī)模很龐大時(shí)，動(dòng)態(tài)規(guī)劃往往面臨極大的計(jì)算量覆劈，這時(shí)使用貪心算法可以高效地得到一個(gè)近似最優(yōu)解保礼，減少計(jì)算量的同時(shí)，得到的解也近似最優(yōu)解

ps 寫到了2019.9.30的最后一分鐘墩崩，撤了撤了TT
歡迎各位大神一起交流偶

此文為作者原創(chuàng)氓英，未經(jīng)許可侯勉，禁止轉(zhuǎn)載