image.png

一、分治，回溯，遞歸，動(dòng)態(tài)規(guī)劃

1.1、遞歸的代碼模板

public void recur(int level, int param) {
    // terminator
    if(level > MAX_LEVEL) {
        // process result
        return;
    }
    
    // process current logic
    process(level, param);
    
    // drill down
    recur(level: level + 1, newParam);
    
    // restore current status
}

1.2、分治（Divide & Conquer）的代碼模板

def divide_conquer(problem, param1, param2, ...):
    # recursion terminator
    if problem is None:
        print_result
        return
    # prepare data
    data = prepare_data(problem)
    subproblems = split_problem(problem, data)
    # conquer subproblems
    subresult1 = self.divide_conquer(subproblems[0], p1, ...)
    subresult2 = self.divide_conquer(subproblems[1], p1, ...)
    subresult3 = self.divide_conquer(subproblems[2], p1, ...)
    ...
    # process and generate the final result
    result = process_result(subresult1, subresult2, subresult2, ...)

1.3、聯(lián)系

1、動(dòng)態(tài)規(guī)劃和遞歸或者分治沒有根本上的區(qū)別（關(guān)鍵看有無最優(yōu)的子結(jié)構(gòu)）。
2、共性：找到重復(fù)子問題。
3、差異性：最優(yōu)子結(jié)構(gòu)，中途可以淘汰次優(yōu)解。

1.4、本質(zhì)

本質(zhì)都是在尋找重復(fù)性，將重復(fù)性轉(zhuǎn)化為計(jì)算機(jī)指令集if else, for, loop, while ...

1.5、總結(jié)

1、人肉遞歸低效，很累。
2、找到最近最簡方法，將其拆解成可重復(fù)解決的問題。
3、數(shù)學(xué)歸納法思維（抵制人肉遞歸的誘惑），先看n=1，n=2時(shí)的情況，然后看f（n）和f（n-1）之間的聯(lián)系。

二、動(dòng)態(tài)規(guī)劃

2.1、定義

1、動(dòng)態(tài)規(guī)劃的英文叫Dynamic programming，翻譯過來叫動(dòng)態(tài)規(guī)劃，翻譯很玄學(xué)，其實(shí)翻譯成動(dòng)態(tài)遞推更容易理解。
2、動(dòng)態(tài)規(guī)劃的本質(zhì)就是將一個(gè)復(fù)雜問題拆解成若干個(gè)子問題進(jìn)行解決。原文為:Simplifying a complicated problem by breaking it down into simpler sub-problems.
3、動(dòng)態(tài)規(guī)劃其實(shí)就是分治+ 最優(yōu)子結(jié)構(gòu)( Divide & Conquer + Optimal substructure)。

2.2、關(guān)鍵點(diǎn)

1、最優(yōu)子結(jié)構(gòu)：公式為，opt[n] = best_of(opt[n-1], opt[n-2], ...)
2、儲(chǔ)存中間狀態(tài)：opt[i]
3、遞推公式（美其名曰：狀態(tài)轉(zhuǎn)移方程或者DP方程）：Fib：opt[i] = opt[n-1] + opt[n-2]. 二維路徑為 opt[i,j] = opt[i+1][j] + opt[i][j+1] , 其中，需要判斷opt[i,j]是否為空。

2.3、小結(jié)

1、打破自己的思維慣性
2、理解復(fù)雜邏輯的關(guān)鍵
3、職業(yè)進(jìn)階的要點(diǎn)要領(lǐng)

三、實(shí)戰(zhàn)例題

例題1：楊輝三角 https://leetcode-cn.com/problems/pascals-triangle/

給定一個(gè)非負(fù)整數(shù) numRows，生成楊輝三角的前 numRows 行。

image

在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。

示例:

輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

思路：

1、動(dòng)態(tài)規(guī)劃，dp存的是結(jié)果，和nums產(chǎn)生聯(lián)系
2、初始方程： dp = [[1] * (i+1) for i in range(num)]，例如 num = 5, 得到[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1, 1]]
3、遞歸方程： dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

時(shí)間復(fù)雜度：O（mn）, m為深度， n為每一層的平均個(gè)數(shù)
空間復(fù)雜度：O（mn），m為深度， n為每一層的平均個(gè)數(shù)

代碼實(shí)現(xiàn)：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        dp = [[1]*(i+1) for i in range(numRows)]
        for i in range(2, numRows):
            for j in range(1, len(dp[i]) - 1):
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        return dp

例題2：打家劫舍 II https://leetcode-cn.com/problems/house-robber-ii/

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都圍成一圈，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。

示例 1：

輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 號(hào)房屋（金額 = 2），然后偷竊 3 號(hào)房屋（金額 = 2）, 因?yàn)樗麄兪窍噜彽摹?br> 示例 2：

輸入：nums = [1,2,3,1]
輸出：4
解釋：你可以先偷竊 1 號(hào)房屋（金額 = 1），然后偷竊 3 號(hào)房屋（金額 = 3）。
偷竊到的最高金額 = 1 + 3 = 4 。
示例 3：

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

思路：

1、動(dòng)態(tài)規(guī)劃
2、初始方程： pre, cur = 0, 0
3、遞推方程： pre, cur = cur, max(pre + nums[i], cur)

時(shí)間復(fù)雜度：O（n）
空間復(fù)雜度：O（1）

代碼實(shí)現(xiàn)：

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        def myrob(nums):
            pre, cur = 0, 0
            for i in range(len(nums)):
                pre, cur = cur, max(pre + nums[i], cur)
            return cur
        return max(myrob(nums[:-1]), myrob(nums[1:]))

例題3： 62. 不同路徑 https://leetcode-cn.com/problems/unique-paths/

image

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

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

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

示例 1：

輸入：m = 3, n = 7
輸出：28
示例 2：

輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達(dá)右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右

思路：
如果沿著邊走，即m=0或者n=0時(shí)，可以走的選擇都是1種，如果不是貼著邊走的話，每一步的走法等于上邊和左邊的走法之和。按著這種思路，可以事先把動(dòng)態(tài)方程的初始方程寫成貼著邊的都是1，其余都是0。當(dāng)然也可以在遍歷的時(shí)候?qū)?。具體看下面代碼實(shí)現(xiàn)。
1、初始方程：dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
2、遞推方程：dp[i][j] = dp[i][j-1] + dp[i-1][j]

時(shí)間復(fù)雜度：O（mn）
空間復(fù)雜度：O（mn）

代碼實(shí)現(xiàn)：

# 寫法一：事先定義好初始方程，貼著邊的都是1，不貼著邊的都是0，拿m=3，n=7 舉例, 得到的初始方程為，[[1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0]]
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[-1][-1]

# 寫法二：直接在遍歷的時(shí)候判斷
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]  

# 寫法三：直接在所有格子填寫1，在第2行第2列開始做累加（等于上1格+左邊1格）
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

例題4： 53. 最大子序和https://leetcode-cn.com/problems/maximum-subarray/

給定一個(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。

思路：

1、初始方程：dp = nums
2、遞推方程：dp[i] = max(dp[]i-1] + nums[i], dp[i])

時(shí)間復(fù)雜度：O（n）
空間復(fù)雜度：O（n）

代碼實(shí)現(xiàn)：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = nums
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], dp[i])
        return max(dp)

例題5： 718. 最長重復(fù)子數(shù)組 https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

給兩個(gè)整數(shù)數(shù)組 A 和 B ，返回兩個(gè)數(shù)組中公共的、長度最長的子數(shù)組的長度。

示例：

輸入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
輸出：3
解釋：
長度最長的公共子數(shù)組是 [3, 2, 1] 。

思路：
思路：動(dòng)態(tài)規(guī)劃dp，數(shù)組元素如果相等，則等于對(duì)角線+1，同時(shí)，比較當(dāng)前值和計(jì)數(shù)值，返回計(jì)數(shù)值和當(dāng)前值的較大者。
1、初始方程：dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
2、遞推方程：dp[i][j] = dp[i-1][j-1] + 1, res = max(res, dp[i][j])

時(shí)間復(fù)雜度：O（mn）， m為A的長度，n為B的長度
空間復(fù)雜度：O（mn）

代碼實(shí)現(xiàn)：

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        res = 0
        dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
        for i in range(len(A)):
            for j in range(len(B)):
                if A[i] == B[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    res = max(res, dp[i][j])
        return res

例題6： 70. 爬樓梯 https://leetcode-cn.com/problems/climbing-stairs/

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個(gè)正整數(shù)。

示例 1：

輸入： 2
輸出： 2
解釋：有兩種方法可以爬到樓頂。

1 階 + 1 階
2 階

示例 2：

輸入： 3
輸出： 3
解釋：有三種方法可以爬到樓頂。

1 階 + 1 階 + 1 階
1 階 + 2 階
2 階 + 1 階

思路：

1、初始方程：dp = [0] * (n+1), dp[0] = dp[1] = 1
2、遞推方程：dp[i] = dp[i-1] + dp[i-2]

時(shí)間復(fù)雜度：O（n）
空間復(fù)雜度：O（n）

代碼實(shí)現(xiàn)：

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]

例題7： 120. 三角形最小路徑和 https://leetcode-cn.com/problems/triangle/

給定一個(gè)三角形，找出自頂向下的最小路徑和。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上。

相鄰的結(jié)點(diǎn) 在這里指的是下標(biāo) 與上一層結(jié)點(diǎn)下標(biāo) 相同或者等于上一層結(jié)點(diǎn)下標(biāo) + 1 的兩個(gè)結(jié)點(diǎn)。

例如，給定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

思路：

自底向上動(dòng)態(tài)規(guī)劃，從三角形的底部倒著遞推至三角形的頂部，逐層進(jìn)行遞推，遞推的規(guī)律為，當(dāng)前元素等于下一層中的相同位置，或者+1位置的最小值中的元素，加上當(dāng)前元素本身。

1、初始方程：dp = [[0] * (n+1) for _ in range(m+1)]
2、遞推方程：dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]

時(shí)間復(fù)雜度：O（mn） m為三角形的深度，n為三角形每行的個(gè)數(shù)
空間復(fù)雜度：O（mn）

代碼實(shí)現(xiàn)：

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        m = len(triangle)
        n = len(triangle[-1])
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(m - 1, -1, -1):
            for j in range(len(triangle[i])):
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
        return dp[0][0]

2021-01-09 更新思路：構(gòu)造dp方程的時(shí)候，可以直接構(gòu)造一個(gè)三角形
初始方程：dp = [[0]*(i + 1) for i in range(len(triangle) + 1)]
完整的代碼為：

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = [[0]*(i + 1) for i in range(len(triangle) + 1)]
        for i in range(len(triangle) -1, -1, -1):
            for j in range(len(triangle[i])):
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
        return dp[0][0]

例題8： 1143. 最長公共子序列 https://leetcode-cn.com/problems/longest-common-subsequence/

給定兩個(gè)字符串 text1 和 text2，返回這兩個(gè)字符串的最長公共子序列的長度。

一個(gè)字符串的子序列是指這樣一個(gè)新的字符串：它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個(gè)字符串的「公共子序列」是這兩個(gè)字符串所共同擁有的子序列。

若這兩個(gè)字符串沒有公共子序列，則返回 0。

示例 1:

輸入：text1 = "abcde", text2 = "ace"
輸出：3
解釋：最長公共子序列是 "ace"，它的長度為 3。
示例 2:

輸入：text1 = "abc", text2 = "abc"
輸出：3
解釋：最長公共子序列是 "abc"，它的長度為 3。
示例 3:

輸入：text1 = "abc", text2 = "def"
輸出：0
解釋：兩個(gè)字符串沒有公共子序列，返回 0。

思路：
動(dòng)態(tài)規(guī)劃，注意dp的初始長度是+1，所以遞推方程中用的是i+1開始，而不是i開始，即dp[i+1][j+1]
1、初始方程：dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
2、遞推方程：相等：dp[i+1][j+1] = dp[i][j] + 1，不相等：dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

時(shí)間復(fù)雜度: O（mn） m為text1的長度，n為text2的長度
空間復(fù)雜度：O（mn）

代碼實(shí)現(xiàn)：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
        return dp[-1][-1]

例題9： 第 k 個(gè)數(shù) https://leetcode-cn.com/problems/get-kth-magic-number-lcci/

有些數(shù)的素因子只有 3，5，7，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找出第 k 個(gè)數(shù)。注意，不是必須有這些素因子，而是必須不包含其他的素因子。例如，前幾個(gè)數(shù)按順序應(yīng)該是 1，3，5，7，9，15，21。

示例 1:

輸入: k = 5

輸出: 9

思路：
動(dòng)態(tài)規(guī)劃
1、初始方程：dp = [0] * k, dp[0] = 1
2、遞推方程：dp[i] = min(dp[num3] * 3, min(dp[num5] * 5, dp[num7] * 7))

時(shí)間復(fù)雜度: O（n）
空間復(fù)雜度：O（n）

代碼實(shí)現(xiàn)：

class Solution:
    def getKthMagicNumber(self, k: int) -> int:
        num3, num5, num7 = 0, 0, 0
        dp = [0] * k
        dp[0] = 1
        for i in range(1, k):
            dp[i] = min(dp[num3] * 3, min(dp[num5] * 5, dp[num7] * 7))
            if dp[i] == dp[num3] * 3:
                num3 += 1
            if dp[i] == dp[num5] * 5:
                num5 += 1
            if dp[i] == dp[num7] * 7:
                num7 += 1
        return dp[-1]

例題11： 64. 最小路徑和 https://leetcode-cn.com/problems/minimum-path-sum/
給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說明：每次只能向下或者向右移動(dòng)一步。

示例 1：

image

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因?yàn)槁窂?1→3→1→1→1 的總和最小。
示例 2：

輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

思路：
思路：dp動(dòng)態(tài)規(guī)劃
初始方程：dp = grid ，因?yàn)橄嗟?，所以可以不顯示寫出來，直接用grid；（說明：但是在工業(yè)級(jí)代碼中還是建議用dp表示，因?yàn)椴粚慸p，直接用grid的話，會(huì)改變?cè)瓉淼娜雲(yún)ⅲ言瓉淼膮?shù)改的面目全非，可能工程中并不希望改變?cè)瓉淼娜雲(yún)?。?br> 遞推方程：i == 0:grid[i][j] += grid[i][j-1]； j == 0: grid[i][j] += grid[i-1][j]； grid[i][j] += min(grid[i-1][j], grid[i][j-1])

時(shí)間復(fù)雜度: O（m*n）
空間復(fù)雜度：O（1）

代碼實(shí)現(xiàn)：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0 and j == 0:
                    continue
                elif i == 0:
                    grid[i][j] += grid[i][j-1]
                elif j == 0:
                    grid[i][j] += grid[i-1][j]
                else:
                    grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[-1][-1]

例題12： 322. 零錢兌換 https://leetcode-cn.com/problems/coin-change/

給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

你可以認(rèn)為每種硬幣的數(shù)量是無限的。

示例 1：

輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
示例 2：

輸入：coins = [2], amount = 3
輸出：-1
示例 3：

輸入：coins = [1], amount = 0
輸出：0
示例 4：

輸入：coins = [1], amount = 1
輸出：1
示例 5：

輸入：coins = [1], amount = 2
輸出：2

思路：
思路：將總數(shù)amount進(jìn)行拆解，每拆解一個(gè)硬幣，則計(jì)數(shù)+1
初始方程：dp = [(amount + 1) for _ in range(amount + 1)]
遞推方程：dp[i] = min(dp[i], dp[i-coin] + 1)

時(shí)間復(fù)雜度: O（m*n），m為硬幣總數(shù)amount， n為不同硬幣的個(gè)數(shù)
空間復(fù)雜度：O（m）

代碼實(shí)現(xiàn)：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [(amount + 1) for _ in range(amount + 1)]
        dp[0] = 0
        for i in range(amount + 1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        if dp[amount] == amount + 1:
            return -1
        return dp[-1]

例題13： 198. 打家劫舍 https://leetcode-cn.com/problems/house-robber/

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

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

示例 1：

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

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

思路：
思路：動(dòng)態(tài)規(guī)劃
初始方程：pre, cur = 0, 0
遞推方程：pre, cur = cur, max(pre + nums[i], cur)
T：O（n）， S：O（1）

時(shí)間復(fù)雜度: O（n）
空間復(fù)雜度：O（1）

代碼實(shí)現(xiàn)：

class Solution:
    def rob(self, nums: List[int]) -> int:
        pre, cur = 0, 0
        for i in range(len(nums)):
            pre, cur = cur, max(pre + nums[i], cur)
        return cur

例題14： 第k個(gè)數(shù) https://leetcode-cn.com/problems/get-kth-magic-number-lcci/

示例 1:

輸入: k = 5

輸出: 9

思路：
思路：動(dòng)態(tài)規(guī)劃dp
初始方程：dp = [0] * k，dp[0] = 1
遞推方程：dp[i] = min(dp[num3]3, min(dp[num5]5, dp[num7]*7))

時(shí)間復(fù)雜度: O（k）
空間復(fù)雜度：O（k）

代碼實(shí)現(xiàn)：

class Solution:
    def getKthMagicNumber(self, k: int) -> int:
        num3, num5, num7 = 0, 0, 0
        dp = [0] * k
        dp[0] = 1
        for i in range(1, k):
            dp[i] = min(dp[num3]*3, min(dp[num5]*5, dp[num7]*7))
            if dp[i] == dp[num3]*3:
                num3 += 1
            if dp[i] == dp[num5]*5:
                num5 += 1
            if dp[i] == dp[num7]*7:
                num7 += 1
        return dp[-1]

數(shù)據(jù)下載：

1、動(dòng)態(tài)規(guī)劃腦圖下載
2、實(shí)戰(zhàn)列題下載

撰寫記錄
2020.10.10-10:57:05-第一次撰寫
2020.12.14-06:55:17-第二次撰寫
2020.12.19-04:18:10-第三次撰寫
2020.12.22-06:12:18-第四次撰寫
2020.12.23-07:18:00-第五次撰寫
2020.12.25-07:32:10-第六次撰寫
2020.12.27-08:59:10-第七次撰寫
2021.01.04-06:58:00-第八次撰寫
2021.01.10-07:39:01-第九次撰寫

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

算法與數(shù)據(jù)結(jié)構(gòu) 之動(dòng)態(tài)規(guī)劃

算法與數(shù)據(jù)結(jié)構(gòu) 之動(dòng)態(tài)規(guī)劃

一、分治，回溯，遞歸，動(dòng)態(tài)規(guī)劃

1.1、遞歸的代碼模板

1.2、分治（Divide & Conquer）的代碼模板

1.3、聯(lián)系

1.4、本質(zhì)

1.5、總結(jié)

二、動(dòng)態(tài)規(guī)劃

2.1、定義

2.2、關(guān)鍵點(diǎn)

2.3、小結(jié)

三、實(shí)戰(zhàn)例題

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

算法與數(shù)據(jù)結(jié)構(gòu) 之 動(dòng)態(tài)規(guī)劃

一、分治，回溯，遞歸，動(dòng)態(tài)規(guī)劃

1.1、遞歸的代碼模板

1.2、分治（Divide & Conquer）的代碼模板

1.3、聯(lián)系

1.4、本質(zhì)

1.5、總結(jié)

二、動(dòng)態(tài)規(guī)劃

2.1、定義

2.2、關(guān)鍵點(diǎn)

2.3、小結(jié)

三、實(shí)戰(zhàn)例題

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

算法與數(shù)據(jù)結(jié)構(gòu) 之動(dòng)態(tài)規(guī)劃

一、分治，回溯，遞歸，動(dòng)態(tài)規(guī)劃

1.2、分治（Divide & Conquer）的代碼模板

1.3、聯(lián)系

1.4、本質(zhì)

1.5、總結(jié)

二、動(dòng)態(tài)規(guī)劃

2.2、關(guān)鍵點(diǎn)

2.3、小結(jié)

三、實(shí)戰(zhàn)例題