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

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 號房屋（金額 = 2）橘蜜，然后偷竊 3 號房屋（金額 = 2）, 因?yàn)樗麄兪窍噜彽摹?br> 示例 2：

輸入：nums = [1,2,3,1]
輸出：4
解釋：你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 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á)右下角陶冷。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

思路：
如果沿著邊走，即m=0或者n=0時(shí)毯辅，可以走的選擇都是1種埂伦，如果不是貼著邊走的話，每一步的走法等于上邊和左邊的走法之和思恐。按著這種思路沾谜，可以事先把動(dòng)態(tài)方程的初始方程寫成貼著邊的都是1膊毁，其余都是0。當(dāng)然也可以在遍歷的時(shí)候?qū)懤嘣纭＞唧w看下面代碼實(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ù)組元素如果相等，則等于對角線+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 階 + 1 階
  2. 2 階

示例 2：

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

  1. 1 階 + 1 階 + 1 階
  2. 1 階 + 2 階
  3. 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è)新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串谒臼。
例如朝刊，"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谊囚，請?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 ，請找出一條從左上角到右下角的路徑肥惭，使得路徑上的數(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è)級代碼中還是建議用dp表示，因?yàn)椴粚慸p揭鳞，直接用grid的話炕贵，會(huì)改變原來的入?yún)ⅲ言瓉淼膮?shù)改的面目全非野崇，可能工程中并不希望改變原來的入?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 號房屋 (金額 = 1) 渠缕，然后偷竊 3 號房屋 (金額 = 3)鸽素。
偷竊到的最高金額 = 1 + 3 = 4 。
示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)亦鳞，接著偷竊 5 號房屋 (金額 = 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/

有些數(shù)的素因子只有 3遭笋，5，7谁不，請?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ī)劃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ù)下載：

撰寫記錄
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-第九次撰寫

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末殿托，一起剝皮案震驚了整個(gè)濱河市霹菊，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌支竹，老刑警劉巖旋廷，帶你破解...
    沈念sama閱讀 207,113評論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異礼搁，居然都是意外死亡饶碘，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,644評論 2贊 381
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門馒吴，熙熙樓的掌柜王于貴愁眉苦臉地迎上來扎运，“玉大人，你說我怎么就攤上這事募书⌒鞔眩” “怎么了测蹲？”我有些...
    開封第一講書人閱讀 153,340評論 0贊 344
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵莹捡，是天一觀的道長。 經(jīng)常有香客問我扣甲，道長篮赢，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 55,449評論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任琉挖，我火速辦了婚禮启泣，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘示辈。我一直安慰自己寥茫，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 64,445評論 5贊 374
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布矾麻。 她就那樣靜靜地躺著纱耻，像睡著了一般。 火紅的嫁衣襯著肌膚如雪险耀。 梳的紋絲不亂的頭發(fā)上弄喘，一...
    開封第一講書人閱讀 49,166評論 1贊 284
  • 城市分裂傳說
    那天，我揣著相機(jī)與錄音甩牺，去河邊找鬼蘑志。 笑死，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的急但。 我是一名探鬼主播澎媒，決...
    沈念sama閱讀 38,442評論 3贊 401
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼波桩！你這毒婦竟也來了旱幼？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 37,105評論 0贊 261
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤突委，失蹤者是張志新（化名）和其女友劉穎柏卤，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體匀油，經(jīng)...
    沈念sama閱讀 43,601評論 1贊 300
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡缘缚，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,066評論 2贊 325
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了敌蚜。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片桥滨。...
    茶點(diǎn)故事閱讀 38,161評論 1贊 334
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖弛车，靈堂內(nèi)的尸體忽然破棺而出齐媒，到底是詐尸還是另有隱情，我是刑警寧澤纷跛，帶...
    沈念sama閱讀 33,792評論 4贊 323
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布喻括，位于F島的核電站，受9級特大地震影響贫奠，放射性物質(zhì)發(fā)生泄漏唬血。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,351評論 3贊 307
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一唤崭、第九天 我趴在偏房一處隱蔽的房頂上張望拷恨。 院中可真熱鬧，春花似錦谢肾、人聲如沸腕侄。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,352評論 0贊 19
  • 一樁弒父案芦疏，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽冕杠。三九已至，卻和暖如春眯分，著一層夾襖步出監(jiān)牢的瞬間拌汇，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,584評論 1贊 261
  • 情欲美人皮
    我被黑心中介騙來泰國打工弊决， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留噪舀，地道東北人魁淳。 一個(gè)月前我還...
    沈念sama閱讀 45,618評論 2贊 355
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像与倡，于是被迫代替她去往敵國和親界逛。 傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,916評論 2贊 344