今天學習的內容是動態規劃算法。

?動態規劃算法（Dynamic Programming，簡稱 DP）是一種通過將復雜問題分解為更小的子問題來求解的算法思想。它主要用于解決具有重疊子問題和最優子結構特性的問題。

?

?

一、動態規劃的基本概念

?

?

1. 最優子結構

?

? 一個復雜問題的最優解可以由其子問題的最優解組合而成。換句話說，問題的最優解包含其子問題的最優解。例如，在背包問題中，如果一個物品被選擇放入背包，那么剩余容量下的最優解就是子問題的最優解。

?

2. 重疊子問題

?

? 在求解過程中，相同的子問題會被多次計算。動態規劃通過存儲這些子問題的解（通常使用一個表格），避免重復計算，從而提高效率。例如，在計算斐波那契數列時，`F(n) = F(n-1) + F(n-2)`，如果不使用動態規劃，會重復計算很多子問題。

?

?

二、動態規劃的解題步驟

?

?

1. 定義狀態

?

?狀態是動態規劃的核心，它表示問題的某個階段的解。狀態的定義需要滿足兩個條件：能夠唯一表示問題的子問題，并且能夠通過狀態之間的關系推導出最終解。

?

2. 狀態轉移方程

?

?狀態轉移方程描述了狀態之間的關系，即如何從已知的狀態推導出新的狀態。這是動態規劃的關鍵部分。

?

3. 初始化

?

? 確定動態規劃的初始化。

經典問題

1.最長遞增子序列（LIS）

?

? 給定一個序列，求其最長遞增子序列的長度。例如，對于序列`[10, 9, 2, 5, 3, 7, 101, 18]`，最長遞增子序列是`[2, 3, 7, 18]`，長度為 4。

?

? 狀態定義：`dp[i]`表示以第`i`個元素結尾的最長遞增子序列的長度。

?

? 狀態轉移方程：

\[

dp[i]=\max{0\le j<i\text{且}a_j<a_i}(dp[j]+1)

\]

其中，`a`是輸入序列。

?

? 初始化：`dp[i] = 1`（每個元素自身可以構成長度為 1 的遞增子序列）。

?

? 計算順序：從`i = 0`到`n - 1`。

?

動態規劃的優化技巧

?

?

1. 空間優化

?

? 在許多情況下，可以將二維動態規劃表優化為一維數組。例如，在背包問題中，如果只關心最終結果，可以將`dp[i][j]`優化為`dp[j]`，通過從后向前更新`dp[j]`來避免覆蓋問題。

?

2. 二分查找優化

?

? 在某些動態規劃問題中，可以結合二分查找來優化狀態轉移。例如，在最長遞增子序列問題中，可以使用二分查找來快速找到合適的插入位置，從而將時間復雜度從\(O(n^2)\)優化到\(O(n\log n)\)。

?

3. 滾動數組

?

? 當狀態轉移只依賴于前幾行時，可以使用滾動數組來減少空間復雜度。例如，在二維動態規劃中，如果狀態轉移只依賴于前一行，可以只使用兩個一維數組交替更新。

?

動態規劃是一種強大的算法思想，通過合理定義狀態和狀態轉移方程，可以高效地解決許多復雜問題。