主要思想：

1、尋找重疊子問題，然后列出狀態(tài)轉(zhuǎn)移方程

2、通過自頂向下的備忘錄或者自底向上的dp table來優(yōu)化

湊零錢問題

k中面值的硬幣，面值分別為[1,2,5]，每種硬幣的數(shù)量無限，再給一個總金額amount。求出最少需要幾枚硬幣湊出這個金額。如果不能湊出，返回-1。

狀態(tài)轉(zhuǎn)移方程：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        res = {}
        res[0] = 0 
        for i in range(1 , amount+1):
            res[i] = float('INF') # 這里要先設(shè)置為無窮大，這樣就會求出最小值
            for coin in coins :
                if i >= coin :
                    res[i] = min(res[i-coin] + 1 , res[i])

        if res[amount]!= float('INF'):
            return res[amount]
        else:
            return -1

以上代碼采用自底向上的方式來消除重疊子問題。

完全平方數(shù)

給定正整數(shù) n，找到若干個完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個數(shù)最少。

給你一個整數(shù) n ，返回和為 n 的完全平方數(shù)的 最少數(shù)量 。

完全平方數(shù) 是一個整數(shù)，其值等于另一個整數(shù)的平方；換句話說，其值等于一個整數(shù)自乘的積。例如，1、4、9 和 16 都是完全平方數(shù)，而 3 和 11 不是。

class Solution:
    def numSquares(self, n: int) -> int:
        max_num = math.floor(math.sqrt(n))
        nums = [i ** 2 for i in range(1 , max_num +1)]
        # 轉(zhuǎn)變成換零錢問題
        res = {}
        res[0] = 0
        for i in range(1, n+1):
            res[i] = float('INF')
            for num in nums :
                if i - num >= 0:
                    res[i] = min(res[i] , res[i-num] + 1)
        if res[i] != float('INF'):
            return res[n]

乘積最大子數(shù)組

給你一個整數(shù)數(shù)組 nums ，請你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個數(shù)字），并返回該子數(shù)組所對應(yīng)的乘積。

示例 1:

輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6。
示例 2:

輸入: [-2,0,-1]
輸出: 0
解釋: 結(jié)果不能為 2, 因為 [-2,-1] 不是子數(shù)組。

動態(tài)規(guī)劃題

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        length = len(nums)
        if length == 1:
            return nums[0]
        dpmax = {}
        dpmin = {}
        dpmax[0] = nums[0]
        dpmin[0] = nums[0]
        # 把問題轉(zhuǎn)化為求以nums[i]結(jié)尾，最大乘積子數(shù)組
        for i in range(1,length) :
            dpmax[i] = max(nums[i] , dpmax[i-1] * nums[i] , dpmin[i-1] * nums[i])
            dpmin[i] = min(nums[i] , dpmax[i-1] * nums[i] , dpmin[i-1] * nums[i])
        
        ans = dpmax[0]
        for i in range(1,len(dpmax)):
            ans = max(ans,dpmax[i])
        return ans

最大子序列和

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。

示例 2：

輸入：nums = [1]
輸出：1

思路：

定義狀態(tài)（子問題）：dp[i]表示以nums[i]為結(jié)尾的連續(xù)子數(shù)組的最大和。注意這里是結(jié)尾！也就是一定會包含nums[i]這個數(shù)在子序列中。

動態(tài)轉(zhuǎn)移方程（描述子問題之間的聯(lián)系）即為：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        if size == 0:
            return 0
        dp = [0 for _ in range(size)]

        dp[0] = nums[0]
        for i in range(1, size):
            if dp[i - 1] >= 0:
                dp[i] = dp[i - 1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)

補(bǔ)充一個對解決動態(tài)規(guī)劃問題非常重要的一個概念：“無后效性”

為了保證計算子問題能夠按照順序、不重復(fù)地進(jìn)行，動態(tài)規(guī)劃要求已經(jīng)求解的子問題不受后續(xù)階段的影響。這個條件也被叫做「無后效性」。換言之，動態(tài)規(guī)劃對狀態(tài)空間的遍歷構(gòu)成一張有向無環(huán)圖，遍歷就是該有向無環(huán)圖的一個拓?fù)湫?。有向無環(huán)圖中的節(jié)點對應(yīng)問題中的「狀態(tài)」，圖中的邊則對應(yīng)狀態(tài)之間的「轉(zhuǎn)移」，轉(zhuǎn)移的選取就是動態(tài)規(guī)劃中的「決策」。

落實在實際解決問題時：

1. 在定義子問題時，不能選擇那種結(jié)果里包含不確定信息的子問題，如果選擇這樣的子問題定義方法，會導(dǎo)致后面的階段求解的子問題無法得到。
2. 解決后效性的方法有兩種（代碼層面）：

• 狀態(tài)數(shù)組增加維度，例如：股票系列問題
• 把狀態(tài)定義的更細(xì)致、更準(zhǔn)確。

打家劫舍問題

leetcode 198. 打家劫舍

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。
偷竊到的最高金額 = 2 + 9 + 1 = 12 。

解題思路：

1. 狀態(tài)：面前每一戶人家的index，選擇：偷這一家還是不偷這一家
2. 兩個選擇中，選取最大的值即為當(dāng)前狀態(tài)的最大money
3. 子問題的定義：dp[i]：前i個房子在滿足條件下能偷竊到的最高金額
4. 狀態(tài)轉(zhuǎn)移方程：

對于前n-1個房子來說，最大金額為dp[i-1]，那么對于第n個房子，有兩種選擇：

• 搶第n個房子，那么第n-1個房子不能搶，那么此時最大金額就是dp[n-2] + nums[n]
• 不搶第n個房子，那么第n-1個房子就是可以搶劫的，那么此時最大金額就是dp[n-1]

那么對于dp[n]= max(dp[n-2]+nums[n],dp[n-1])

4. base 情況：dp[0] = 0，dp[1]=nums[0]
5. 返回結(jié)果：dp最后一個元素值

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp={}
        n = len(nums)
        dp[0] = nums[0]
        dp[-1] = 0
        for i in range(1,n):
            dp[i] = max(dp[i-1] , nums[i] + dp[i-2])
        return dp[n-1]

以上解決辦法為自底向上的方法，下面貼出用遞歸自頂向下的方式，并用備忘錄進(jìn)行剪枝，從而解決運行時間。

class Solution:
    def rob(self, nums: List[int]) -> int:
        length = len(nums)
        memo = {}
        memo[-1] = 0
        memo[0] = nums[0]
        
        def helper(end): # 求前end個房子，搶劫到的最大金額
            if end in memo:
                return memo[end]
            not_do = helper(end-1)
            do = helper(end-2)+nums[end]
            res = max(do,not_do)
            memo[end] = res
            return res
        
        return helper(length-1)

leetcode213. 打家劫舍2

房屋并不是線性的數(shù)組了，而是圍成一個圈，也就是如果搶劫了最后一戶人家，那么就不能搶第一戶人家；如果搶劫了第一戶人家，那么就不能搶劫第二戶人家。

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp1={}
        n = len(nums)
        if n == 1: return nums[0]
        # 不偷第一家
        dp1[0] = 0
        dp1[-1] = 0
        for i in range(1,n):
            dp1[i] = max(dp1[i-1],nums[i] + dp1[i-2])
        # 不偷最后一家
        dp2={}
        dp2[0],dp2[-1] = nums[0],0
        for i in range(1,n-1):
            dp2[i] = max(dp2[i-1],nums[i] + dp2[i-2])
            
        return max(dp1[n-1],dp2[n-2])

以上兩種情況的區(qū)別在于：不偷第一家的話，dp[0]=0, 而如果偷的話dp[0] = nums[0]

leetcode337. 打家劫舍3

這里房屋如何布置又變化了一下，變成是二叉樹的分布。二叉樹的遍歷只能從root開始，才能到葉子節(jié)點。不能直接通過index獲取元素。所以這里只能采用遞歸的方式，自頂向下的解決該問題。

示例 1:

輸入: [3,2,3,null,3,null,1]

 3
/ \

2 3
\ \
3 1
輸出: 7
解釋: 小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7.

class Solution:
    def rob(self, root: TreeNode) -> int:
        memo = {}
        def helper(root):
            if root== None: return 0
            if root in memo: return memo[root]
            do_it = root.val
            if root.left:
                do_it += helper(root.left.left) + helper(root.left.right)
            if root.right:
                do_it += helper(root.right.left) + helper(root.right.right)
            
            not_do_it = helper(root.left) + helper(root.right)

            res = max(do_it,not_do_it)
            memo[root] = res
            return res
        helper(root)
        return memo[root]

62. 不同路徑1

一個機(jī)器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為 “Start” ）。

機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。

問總共有多少條不同的路徑？

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        for i in range(0, m):
            for j in range(0, n):
                if i == 0 and j == 0: continue
                if i == 0:
                    dp[i][j] = dp[i][j - 1]
                elif j == 0:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m-1][n-1]

這題注意1）臨界點的特殊處理 2）還有dp數(shù)組在創(chuàng)建的時候要用列表推導(dǎo)式，涉及到python中的淺拷貝和深拷貝問題

63.不同路徑2

一個機(jī)器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）。

機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。

現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 0 if obstacleGrid[0][0] == 1 else 1 # 這里注意初始值要相對于前面的代碼需要修改
        for i in range(0, m):
            for j in range(0, n):
                if obstacleGrid[i][j] == 1: continue
                if i == 0 and j == 0: continue
                if i == 0:
                    if obstacleGrid[i][j-1] == 1:
                        dp[i][j] = 0
                    else: 
                        dp[i][j] = dp[i][j - 1]
                elif j == 0:
                    if obstacleGrid[i-1][j] == 1:
                        dp[i][j] = 0
                    else:
                        dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m-1][n-1]

這里有個微妙的地方：寫完代碼之后我在思考為什么if obstacleGrid[i][j] == 1: continue沒有對dp[i][j]賦值為0也能提交正確，后來想到我初始化dp數(shù)組的時候，所有路徑的值全部初始化的是0，所以這里不將dp[i][j]置為0也是正確的。

最小路徑和

給定一個包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說明：每次只能向下或者向右移動一步。

這一題我一開始的想法是圖搜索算法，也就是廣度優(yōu)先搜索，但后來看了下筆記，發(fā)現(xiàn)這道題目和廣度優(yōu)先搜素算法不一樣的地方在于：廣度優(yōu)先算法不能處理圖中帶有權(quán)重的圖搜索問題，如果想要處理無環(huán)有權(quán)重的圖搜索問題，要用Dijkstra算法。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[i][j] = grid[0][0]
                elif i==0:
                    dp[i][j] = dp[i][j-1] + grid[i][j]
                elif j==0:
                    dp[i][j] = dp[i-1][j] + grid[i][j]
                else:
                    dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
        return dp[m-1][n-1]