零 算法介紹

動(dòng)態(tài)規(guī)劃（Dynamic Programming，DP）是一種解決最優(yōu)化問(wèn)題的算法思想，通過(guò)將問(wèn)題分解成更小的子問(wèn)題來(lái)解決。其核心思想是將一個(gè)問(wèn)題分解成更小的、相互獨(dú)立的子問(wèn)題，然后將子問(wèn)題的解組合起來(lái)，形成原問(wèn)題的解。但與之前的算法不一樣的是，動(dòng)態(tài)規(guī)劃強(qiáng)調(diào)的是動(dòng)態(tài)的過(guò)程，即在程序計(jì)算時(shí)，會(huì)出現(xiàn)隨程序運(yùn)行而變化的參數(shù)輔助程序完成算法計(jì)算。

動(dòng)態(tài)規(guī)劃算法的主要特點(diǎn)包括：

1. 重疊子問(wèn)題：動(dòng)態(tài)規(guī)劃算法解決的問(wèn)題通常包含許多重疊的子問(wèn)題。

2. 狀態(tài)轉(zhuǎn)移方程：動(dòng)態(tài)規(guī)劃算法通常使用狀態(tài)轉(zhuǎn)移方程來(lái)描述問(wèn)題的狀態(tài)和狀態(tài)轉(zhuǎn)移關(guān)系。

3. 自底向上：動(dòng)態(tài)規(guī)劃算法通常采用自底向上的方法，即從最小的子問(wèn)題開(kāi)始解決，逐步解決更大的子問(wèn)題。

動(dòng)態(tài)規(guī)劃算法的應(yīng)用范圍非常廣泛，包括：

1. 組合優(yōu)化問(wèn)題：如背包問(wèn)題、旅行商問(wèn)題等。

2. 序列問(wèn)題：如最長(zhǎng)公共子序列、最長(zhǎng)遞增子序列等。

3. 圖論問(wèn)題：如最短路徑問(wèn)題、最小生成樹(shù)問(wèn)題等。

4. 動(dòng)態(tài)規(guī)劃在游戲、人工智能、計(jì)算機(jī)圖形學(xué)等領(lǐng)域也有廣泛應(yīng)用。

動(dòng)態(tài)規(guī)劃算法有很多變種，如線性動(dòng)態(tài)規(guī)劃、樹(shù)形動(dòng)態(tài)規(guī)劃、網(wǎng)格動(dòng)態(tài)規(guī)劃等。在實(shí)際應(yīng)用中，需要根據(jù)問(wèn)題的特點(diǎn)選擇合適的動(dòng)態(tài)規(guī)劃算法。

一 例題介紹 使用最小花費(fèi)爬樓梯

給你一個(gè)整數(shù)數(shù)組 cost ，其中 cost[i] 是從樓梯第 i 個(gè)臺(tái)階向上爬需要支付的費(fèi)用。一旦你支付此費(fèi)用，即可選擇向上爬一個(gè)或者兩個(gè)臺(tái)階。

你可以選擇從下標(biāo)為 0 或下標(biāo)為 1 的臺(tái)階開(kāi)始爬樓梯。

請(qǐng)你計(jì)算并返回達(dá)到樓梯頂部的最低花費(fèi)。

示例 1：

輸入：cost = [10,15,20]
輸出：15
解釋：你將從下標(biāo)為 1 的臺(tái)階開(kāi)始。
- 支付 15 ，向上爬兩個(gè)臺(tái)階，到達(dá)樓梯頂部。
總花費(fèi)為 15 。

問(wèn)題分析

動(dòng)態(tài)規(guī)劃強(qiáng)調(diào)的是動(dòng)態(tài)的過(guò)程， 故當(dāng)我們?cè)倏催@道題目的時(shí)候，我們的關(guān)注點(diǎn)是 一旦你支付此費(fèi)用，即可選擇向上爬一個(gè)或者兩個(gè)臺(tái)階。 當(dāng)我們轉(zhuǎn)換一下思路，則是：當(dāng)前臺(tái)階的價(jià)值應(yīng)該是由前一個(gè)臺(tái)階或是前前一個(gè)臺(tái)階決定的。如果這套規(guī)則適用的話，則代表第N階的臺(tái)階等于total[n] = min(total[n-1]+cost[n-1], total[n-2]+cost[n-2])。即，當(dāng)前臺(tái)階的最低花費(fèi)應(yīng)該是在上兩級(jí)臺(tái)階的最小開(kāi)銷中進(jìn)行選擇。

代碼呈現(xiàn)如下：

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:old1, old2 = 0, 0     # 初始化前前一個(gè)臺(tái)階和前一個(gè)臺(tái)階的初始價(jià)格for i in cost:        # 對(duì)所有臺(tái)階遍歷temp = i + min(old1, old2)     # 第N個(gè)臺(tái)階的花費(fèi)是當(dāng)前第N個(gè)臺(tái)階的價(jià)格加上前兩級(jí)臺(tái)階中小的那個(gè)old1, old2 = old2, temp        # 迭代return min(old1, old2)

Leetcode例題與思路

接下來(lái)，我們列舉關(guān)于Leetcode的幾道例題，并通過(guò)動(dòng)態(tài)規(guī)劃的方式進(jìn)行求解：

118. 楊輝三角

        11 11 2 11 3 3 11 4 6 4 1

解題思路

這道題目是最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃題目，對(duì)于第N行來(lái)說(shuō)，其第1個(gè)和最后一個(gè)應(yīng)當(dāng)為1，其余位置可以通過(guò)上一行中當(dāng)前位置和當(dāng)前位置的下一位置兩個(gè)元素求和完成。轉(zhuǎn)換成代碼如下所示：

題解

class Solution:def generate(self, numRows: int) -> List[List[int]]:res = []for i in range(numRows):row = [None for _ in range(i + 1)]row[0], row[-1] = 1, 1for j in range(1, len(row) - 1):row[j] = res[i - 1][j - 1] + res[i - 1][j]res.append(row)return res

53. 最大子數(shù)組和

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

解題思路

由于這邊僅需要找到最大和，無(wú)需判斷位置。故我們僅需判斷最大值作為我們的判斷。那么最大子數(shù)組和應(yīng)該有什么特點(diǎn)呢？其實(shí)從這道題目中我們就會(huì)發(fā)現(xiàn)從哪開(kāi)始到哪結(jié)束是不重要的。需要關(guān)注的是在第N個(gè)元素的位置，我們之前的元素和大于零還是小于零。什么意思呢？即之前元素之和如果小于0，那么對(duì)于后續(xù)元素求和只有負(fù)面效果，故可以直接丟棄從第N個(gè)元素開(kāi)始重新統(tǒng)計(jì)。而我們只需要在這個(gè)過(guò)程中，找到累計(jì)和最大的值就可以了。由題目的提示可知，-10^4 <= nums[i] <= 10^4。故我們可以選擇-10000作為初始化：

題解

class Solution:def maxSubArray(self, nums: List[int]) -> int:temp, max_value = -10000, -10000for i in nums:temp = max(temp + i, i)max_value = max(temp, max_value)return max_value

96. 不同的二叉搜索樹(shù)

解題思路

首先我們需要明確一個(gè)概念，什么是二叉搜索樹(shù)：

二叉搜索樹(shù)（Binary Search Tree, BST）是一種特殊的二叉樹(shù)，它的每個(gè)節(jié)點(diǎn)都有一個(gè)關(guān)鍵值，并且所有節(jié)點(diǎn)的關(guān)鍵值滿足以下性質(zhì)：

1. 節(jié)點(diǎn)的左子樹(shù)（如果存在）的關(guān)鍵值都小于節(jié)點(diǎn)的關(guān)鍵值。

2. 節(jié)點(diǎn)的右子樹(shù)（如果存在）的關(guān)鍵值都大于節(jié)點(diǎn)的關(guān)鍵值。

3. 節(jié)點(diǎn)的左右子樹(shù)（如果存在）也都是二叉搜索樹(shù)。

這種結(jié)構(gòu)使得二叉搜索樹(shù)在查找、插入和刪除操作方面具有較高的效率。

那么面對(duì)這樣一道題，我們?cè)撊绾吻蠼饽?#xff1f;首先，我們需要明確一個(gè)問(wèn)題，就是對(duì)于N個(gè)節(jié)點(diǎn)的二叉樹(shù)，我們可以把這個(gè)二叉樹(shù)從節(jié)點(diǎn)切分，分為成小于該長(zhǎng)度的二叉樹(shù)來(lái)求解。換句話說(shuō)，我們?cè)诿鎸?duì)一個(gè)4節(jié)點(diǎn)的二叉搜索樹(shù)，可以看作013[代表左子樹(shù)0，根節(jié)點(diǎn)1，右節(jié)點(diǎn)3]，112, 211 , 310。所以我們僅需要得到1節(jié)點(diǎn)，2節(jié)點(diǎn)和3節(jié)點(diǎn)的樹(shù)就可以推出4節(jié)點(diǎn)的數(shù)量。那么我們可以快速推出，0節(jié)點(diǎn)僅存在1種排列，1節(jié)點(diǎn)僅存在1種排列。從2節(jié)點(diǎn)開(kāi)始，我們可以通過(guò)公式進(jìn)行推理：N節(jié)點(diǎn)的樹(shù)可以看作N個(gè)根和他們的左右子樹(shù)。故，我們可以通過(guò)左子樹(shù)的種類乘以右子樹(shù)的種類得到每個(gè)節(jié)點(diǎn)存在子樹(shù)的個(gè)數(shù)。繼續(xù)以4節(jié)點(diǎn)樹(shù)為例，可以分為013，112, 211 , 310。當(dāng)我們知道0，1，2，3個(gè)節(jié)點(diǎn)的數(shù)量時(shí)，就可以得到013[1*5]，112[1*2], 211[2*1] , 310[5*1]。故四節(jié)點(diǎn)可以構(gòu)建5+2+2+5=14個(gè)排列。

題解

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

322. 零錢(qián)兌換

解題思路

這道題目可以轉(zhuǎn)換成走樓梯的思路。如果還不能get到這個(gè)思路的話，我們?cè)偌?xì)說(shuō)一下：

針對(duì)N塊錢(qián)，湊出來(lái)的方法必然是考慮N塊錢(qián)前一步的狀態(tài)，即N塊錢(qián)減去coins的狀態(tài)下需要多少步。所以我們從coins最小的儲(chǔ)蓄開(kāi)始執(zhí)行，通過(guò)對(duì)比上一步的所有狀態(tài)，選擇其中需要部署最小的作為自己的結(jié)果，一直到amount，得到最終結(jié)果。

題解

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:answer = [-1 for i in range(amount+1)]             # 初始化所有狀態(tài)answer[0] = 0                                      # 初始化0，這樣coins中的所有元素的步長(zhǎng)都為1for i in range(min(coins), amount+1):              # 計(jì)算到amount的步長(zhǎng)mins = 2**31for j in coins:                                # 對(duì)比coins中的所有狀態(tài)if i - j >= 0 and answer[i - j] > -1:      # 當(dāng)上一狀態(tài)合法且存在時(shí)，獲得最小步數(shù)mins = min(answer[i - j] + 1, mins)answer[i] = mins if mins != 2**31 else -1      # 更新當(dāng)前狀態(tài)return answer[-1]

124. 二叉樹(shù)中的最大路徑和

解題思路

這是一道將動(dòng)態(tài)規(guī)劃運(yùn)用到樹(shù)上的一道題，結(jié)合了樹(shù)的搜索，故還需要用到遞歸的方法進(jìn)行搜索。

我們對(duì)其中任意節(jié)點(diǎn)進(jìn)行思考，如何判斷當(dāng)前節(jié)點(diǎn)以下的樹(shù)節(jié)點(diǎn)應(yīng)當(dāng)被省略？即會(huì)降低全局解的情況，也就是當(dāng)前節(jié)點(diǎn)聯(lián)通的路徑小于0的情況下。那怎么得到當(dāng)前節(jié)點(diǎn)的聯(lián)通路徑呢？即根節(jié)點(diǎn)和左子樹(shù)與右子樹(shù)中較大的值的和。故我們需要注意，**左子樹(shù)和右子樹(shù)的返回結(jié)果是必然大于0的，否則就沒(méi)有鏈接的必要。**那如果不回調(diào)的話，最大聯(lián)通樹(shù)應(yīng)該是當(dāng)前節(jié)點(diǎn)加上左節(jié)點(diǎn)加上右節(jié)點(diǎn)的值，如果當(dāng)前值大于已知的最大值，那么就可以替換當(dāng)前的最大值。

題解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:self.answer = -1000self.maxroot(root)return self.answerdef maxroot(self, root):if root == None:return 0else:left = self.maxroot(root.left)right = self.maxroot(root.right)self.answer = max(self.answer, root.val + left + right)return max(max(left, right) + root.val, 0)

以上就是最基礎(chǔ)的動(dòng)態(tài)規(guī)劃，動(dòng)態(tài)規(guī)劃的題目難度非常大，后續(xù)有精力會(huì)詳細(xì)拆開(kāi)，深入剖析。