零 算法介紹

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

動態(tài)規(guī)劃算法的主要特點包括：

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

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

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

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

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

2. 序列問題：如最長公共子序列、最長遞增子序列等。

3. 圖論問題：如最短路徑問題、最小生成樹問題等。

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

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

一 例題介紹 使用最小花費爬樓梯

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

你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。

請你計算并返回達到樓梯頂部的最低花費。

示例 1：

輸入：cost = [10,15,20]
輸出：15
解釋：你將從下標為 1 的臺階開始。
- 支付 15 ，向上爬兩個臺階，到達樓梯頂部。
總花費為 15 。

問題分析

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

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

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

Leetcode例題與思路

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

118. 楊輝三角

        11 11 2 11 3 3 11 4 6 4 1

解題思路

這道題目是最簡單的動態(tài)規(guī)劃題目，對于第N行來說，其第1個和最后一個應當為1，其余位置可以通過上一行中當前位置和當前位置的下一位置兩個元素求和完成。轉(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 。

解題思路

由于這邊僅需要找到最大和，無需判斷位置。故我們僅需判斷最大值作為我們的判斷。那么最大子數(shù)組和應該有什么特點呢？其實從這道題目中我們就會發(fā)現(xiàn)從哪開始到哪結(jié)束是不重要的。需要關(guān)注的是在第N個元素的位置，我們之前的元素和大于零還是小于零。什么意思呢？即之前元素之和如果小于0，那么對于后續(xù)元素求和只有負面效果，故可以直接丟棄從第N個元素開始重新統(tǒng)計。而我們只需要在這個過程中，找到累計和最大的值就可以了。由題目的提示可知，-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. 不同的二叉搜索樹

解題思路

首先我們需要明確一個概念，什么是二叉搜索樹：

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

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

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

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

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

那么面對這樣一道題，我們該如何求解呢？首先，我們需要明確一個問題，就是對于N個節(jié)點的二叉樹，我們可以把這個二叉樹從節(jié)點切分，分為成小于該長度的二叉樹來求解。換句話說，我們在面對一個4節(jié)點的二叉搜索樹，可以看作013[代表左子樹0，根節(jié)點1，右節(jié)點3]，112, 211 , 310。所以我們僅需要得到1節(jié)點，2節(jié)點和3節(jié)點的樹就可以推出4節(jié)點的數(shù)量。那么我們可以快速推出，0節(jié)點僅存在1種排列，1節(jié)點僅存在1種排列。從2節(jié)點開始，我們可以通過公式進行推理：N節(jié)點的樹可以看作N個根和他們的左右子樹。故，我們可以通過左子樹的種類乘以右子樹的種類得到每個節(jié)點存在子樹的個數(shù)。繼續(xù)以4節(jié)點樹為例，可以分為013，112, 211 , 310。當我們知道0，1，2，3個節(jié)點的數(shù)量時，就可以得到013[1*5]，112[1*2], 211[2*1] , 310[5*1]。故四節(jié)點可以構(gòu)建5+2+2+5=14個排列。

題解

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. 零錢兌換

解題思路

這道題目可以轉(zhuǎn)換成走樓梯的思路。如果還不能get到這個思路的話，我們再細說一下：

針對N塊錢，湊出來的方法必然是考慮N塊錢前一步的狀態(tài)，即N塊錢減去coins的狀態(tài)下需要多少步。所以我們從coins最小的儲蓄開始執(zhí)行，通過對比上一步的所有狀態(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中的所有元素的步長都為1for i in range(min(coins), amount+1):              # 計算到amount的步長mins = 2**31for j in coins:                                # 對比coins中的所有狀態(tài)if i - j >= 0 and answer[i - j] > -1:      # 當上一狀態(tài)合法且存在時，獲得最小步數(shù)mins = min(answer[i - j] + 1, mins)answer[i] = mins if mins != 2**31 else -1      # 更新當前狀態(tài)return answer[-1]

124. 二叉樹中的最大路徑和

解題思路

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

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

題解

# 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ǔ)的動態(tài)規(guī)劃，動態(tài)規(guī)劃的題目難度非常大，后續(xù)有精力會詳細拆開，深入剖析。