一文讀懂動態規劃：多種經典問題和思路

一、動態規劃算法的思想與核心概念框架

1. 動態規劃的基本思想

動態規劃（Dynamic Programming, DP）是一種通過將復雜問題分解為重疊子問題，并利用子問題的解來高效解決原問題的方法。其核心思想是避免重復計算，通過存儲中間結果（即 “記憶化”）來優化遞歸過程，本質上是空間換時間的策略。
與分治法的區別在于：動態規劃允許子問題重疊，而分治法要求子問題獨立；動態規劃通常自底向上求解，而分治法常采用自頂向下遞歸。

2.核心概念框架

動態規劃的核心概念可拆解為以下要素：

問題特性
- 最優子結構：問題的最優解包含子問題的最優解（如斐波那契數列中 f (n) 的最優解依賴 f (n-1) 和 f (n-2)）
- 重疊子問題：子問題會被重復計算多次（如計算 f (5) 時需要重復計算 f (3)）
狀態定義
- 用dp[i]表示與問題規模i相關的狀態，是動態規劃的核心建模步驟
- 狀態需具備無后效性：當前狀態只與之前的狀態有關，與后續狀態無關
狀態轉移方程
- 描述狀態之間的遞推關系，是動態規劃的數學表達
- 例如：斐波那契數列的轉移方程為dp[i] = dp[i-1] + dp[i-2]
初始條件
- 定義最小規模子問題的解（如斐波那契數列中dp[0]=0, dp[1]=1）
結果提取
- 根據問題要求，從狀態數組中獲取最終解（可能是dp[n]或數組中的最大值等）

3. 狀態轉移方程設計方法與技巧

設計步驟
- 分析問題結構：確定是否具有最優子結構和重疊子問題
- 定義狀態：明確dp[i]表示的含義（關鍵在于 “i” 的語義）
- 推導轉移關系：從子問題解構建當前問題解
- 設定初始條件：處理邊界情況
- 確定計算順序：自底向上填充狀態數組
核心技巧
- 一維狀態轉移
  - 適用于子問題僅依賴前 1 或前 k 個狀態的場景
  - 技巧：用滾動數組優化空間（如斐波那契數列只需保存前兩個值）
- 二維狀態轉移
  - 適用于雙維度約束問題（如背包問題的 “重量” 和 “價值”）
  - 技巧：注意遍歷順序（按行或按列），避免狀態覆蓋
- 區間 DP
  - 狀態定義為dp[i][j]表示區間 [i,j] 的最優解
  - 轉移方程：dp[i][j] = max(dp[i][k] + dp[k+1][j] + …)，其中 k 為區間分割點
- 狀態壓縮
  - 當狀態只與前幾行 / 列相關時，用一維數組替代二維數組
  - 例如：完全背包問題中用 “倒序遍歷” 實現空間優化
- 記憶化搜索（自頂向下）
  - 用遞歸 + 緩存實現動態規劃，適合子問題調用順序不明確的場景
  - LeetCode 中可用@lru_cache裝飾器快速實現

二、股票問題的動態規劃解法框架

股票買賣問題是動態規劃的經典應用場景，通過調整交易次數限制、冷凍期、手續費等條件，可以衍生出多種變體。下面給出股票問題的通用解法框架，并針對不同變體詳細分析狀態轉移方程和代碼實現。

2.1 通用解法框架

狀態定義：
dp[i][k][0]：第 i 天結束，最多完成 k 筆交易，當前不持有股票的最大利潤
dp[i][k][1]：第 i 天結束，最多完成 k 筆交易，當前持有股票的最大利潤
通用轉移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])  # 不操作 or 賣出
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])  # 不操作 or 買入（消耗一筆交易）

初始條件：

dp[0][k][0] = 0  # 第0天不持有，利潤為0，所有k
dp[0][k][1] = -prices[0]  # 第0天持有，說明買入了，利潤為負
dp[i][0][0] = 0  # k=0表示不能交易，利潤為0
dp[i][0][1] = -∞  # 不可能持有股票（無法交易）,買入算一次交易

最終結果：
dp[n-1][K][0]，其中 n 為天數，K 為最大交易次數上限

2.2 具體變體及實現

1. 買賣股票的最佳時機（LeetCode 121，最多 1 次交易）
狀態轉移方程：

dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i])  # k=0時利潤為0，故簡化為-prices[i]

空間優化后的代碼

def maxProfit(prices):n = len(prices)if n == 0:return 0dp_i_0 = 0dp_i_1 = float('-inf')for i in range(n):dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])dp_i_1 = max(dp_i_1, -prices[i])return dp_i_0

其實本題還可以從貪心算法理解，dp_i_1記錄當前最小股票價格，即最大的max(do_i_1, -prices[i])，然后沒過一天記錄如果賣掉的最大收益，即max(dp_i_0, dp_i_1 + prices[i])。

2. 買賣股票的最佳時機 II（LeetCode 122，不限交易次數）
狀態轉移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
# 由于k不限制，可以省略k維度，簡化為：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

空間優化后的代碼

def maxProfit(prices):n = len(prices)if n == 0:return 0dp_i_0 = 0dp_i_1 = float('-inf')for i in range(n):temp = dp_i_0dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])dp_i_1 = max(dp_i_1, temp - prices[i])return dp_i_0

3. 買賣股票的最佳時機 III（LeetCode 123，最多 2 次交易）
其實限制次數的股票問題類似于背包問題，要考慮兩種約束。具體背包問題下面介紹。
狀態轉移方程：

dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i])  # 初始買入時k=0，利潤為0

空間優化后的代碼

def maxProfit(prices):n = len(prices)if n == 0:return 0# 初始化四個狀態dp_i10 = 0  # 第一次賣出dp_i11 = float('-inf')  # 第一次買入dp_i20 = 0  # 第二次賣出dp_i21 = float('-inf')  # 第二次買入for i in range(n):dp_i20 = max(dp_i20, dp_i21 + prices[i])dp_i21 = max(dp_i21, dp_i10 - prices[i])dp_i10 = max(dp_i10, dp_i11 + prices[i])dp_i11 = max(dp_i11, -prices[i])return dp_i20

4. 買賣股票的最佳時機 IV（LeetCode 188，最多 k 次交易）
狀態轉移方程：
與通用框架一致，但需處理 k 過大導致內存溢出的問題（當 k >= n/2 時，等價于不限次數交易）
代碼實現

def maxProfit(k, prices):n = len(prices)if n == 0 or k == 0:return 0# 當k >= n/2時，等價于不限次數交易，用貪心算法if k >= n // 2:profit = 0for i in range(1, n):if prices[i] > prices[i-1]:profit += prices[i] - prices[i-1]return profit# 否則使用動態規劃dp = [[[0] * 2 for _ in range(k+1)] for __ in range(n)]for i in range(n):for j in range(1, k+1):if i == 0:dp[0][j][0] = 0dp[0][j][1] = -prices[0]continuedp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])return dp[n-1][k][0]

5. 最佳買賣股票時機含冷凍期（LeetCode 309，不限次數但賣出后需冷凍 1 天）
狀態定義擴展：

dp[i][0]：第 i 天結束不持有且不在冷凍期的最大利潤
dp[i][1]：第 i 天結束持有股票的最大利潤
dp[i][2]：第 i 天結束不持有且在冷凍期的最大利潤
狀態轉移方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][2])  # 前一天不持有（無論是否冷凍）
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])  # 前一天持有 或 前一天不冷凍今天買入
dp[i][2] = dp[i-1][1] + prices[i]  # 前一天持有今天賣出，進入冷凍期

空間優化后的代碼

def maxProfit(prices):n = len(prices)if n == 0:return 0dp_i_0 = 0  # 不持有且不在冷凍期dp_i_1 = float('-inf')  # 持有dp_i_2 = 0  # 不持有且在冷凍期for i in range(n):temp = dp_i_0dp_i_0 = max(dp_i_0, dp_i_2)dp_i_1 = max(dp_i_1, temp - prices[i])dp_i_2 = dp_i_1 + prices[i]return max(dp_i_0, dp_i_2)

6. 買賣股票的最佳時機含手續費（LeetCode 714，不限次數但每次交易有手續費）
狀態轉移方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)  # 賣出時扣除手續費
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

空間優化后的代碼

def maxProfit(prices, fee):n = len(prices)if n == 0:return 0dp_i_0 = 0dp_i_1 = float('-inf')for i in range(n):temp = dp_i_0dp_i_0 = max(dp_i_0, dp_i_1 + prices[i] - fee)dp_i_1 = max(dp_i_1, temp - prices[i])return dp_i_0

三、總結與擴展技巧
狀態設計技巧：
當問題引入新限制（如冷凍期、手續費）時，可擴展狀態維度或新增狀態變量
對于交易次數 k，若 k 較大（k >= n/2），可轉化為不限次數問題以優化空間
空間優化策略：
當狀態轉移僅依賴前一天的狀態時，可用常數級變量替代二維數組
對于多狀態問題（如含冷凍期），維護多個變量記錄不同狀態
初始化注意事項：
持有股票狀態初始化為負無窮，表示初始不可能持有股票
交易次數為 0 時，利潤必須為 0，持有狀態為負無窮
掌握這些模式后，遇到新的股票問題變體時，只需調整狀態定義和轉移方程即可快速解決。

三、背包問題詳解：從基礎到進階

背包問題是動態規劃中的經典問題類型，其核心是在資源有限的情況下最大化收益。下面將從最基礎的 0-1 背包問題開始，逐步引入變種和優化方法。

3.1 0-1 背包問題（基礎模型）

問題描述：
給定一組物品，每個物品有重量w[i]和價值v[i]，以及一個容量為C的背包。要求選擇若干物品放入背包，使得總重量不超過容量C，且總價值最大。每個物品只能選擇一次（0-1 選擇）。
狀態定義：
dp[i][j]表示前i個物品放入容量為j的背包中能獲得的最大價值。準確地來說應該是考慮前i個物品（前i個物品可供選擇的情況下），即并非前i個物品都要放入背包。
狀態轉移方程：

dp[i][j] = max(dp[i-1][j],          # 不選第i個物品dp[i-1][j-w[i]] + v[i]  # 選第i個物品（前提是j >= w[i]）)

初始條件：

dp[0][j] = 0：沒有物品時，價值為 0
dp[i][0] = 0：背包容量為 0 時，價值為 0

代碼實現：

def knapsack_01(weights, values, C):n = len(weights)dp = [[0] * (C + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, C + 1):if j < weights[i-1]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])return dp[n][C]

復雜度分析：

時間復雜度：O (nC)
空間復雜度：O (nC)

3.2 空間優化：滾動數組

觀察狀態轉移方程，發現dp[i][j]只依賴于dp[i-1][j]和dp[i-1][j-w[i]]，即只與上一行有關。因此可以用一維數組優化空間：
優化后狀態轉移方程：

dp[j] = max(dp[j], dp[j-w[i]] + v[i])  # 逆序更新j

代碼實現

def knapsack_01_optimized(weights, values, C):n = len(weights)dp = [0] * (C + 1)for i in range(n):for j in range(C, weights[i] - 1, -1):  # 逆序遍歷，避免重復選擇同一物品dp[j] = max(dp[j], dp[j - weights[i]] + values[i])return dp[C]

復雜度分析：

時間復雜度：O (nC)
空間復雜度：O ?

3.3 完全背包問題

問題描述：
與 0-1 背包的區別在于，每種物品可以無限次選取。
狀態轉移方程：

dp[i][j] = max(dp[i-1][j],          # 不選第i個物品dp[i][j-w[i]] + v[i]  # 選第i個物品（可重復選，因此是dp[i]而非dp[i-1]）)

一維數組優化

dp[j] = max(dp[j], dp[j-w[i]] + v[i])  # 正序更新j

代碼實現

def knapsack_complete(weights, values, C):n = len(weights)dp = [0] * (C + 1)for i in range(n):for j in range(weights[i], C + 1):  # 正序遍歷，允許重復選擇同一物品dp[j] = max(dp[j], dp[j - weights[i]] + values[i])return dp[C]

3.4 多重背包問題

問題描述：
每種物品有有限的數量count[i]，可以選擇 0 到count[i]次。
樸素解法：
將每種物品拆分成count[i]個獨立物品，轉化為 0-1 背包問題。
二進制優化：
將每種物品拆分成若干組，每組代表一個二進制數，從而將時間復雜度從 $(nC\sum count [i])$ 優化到 $(nC\sum \log (count [i]))$ 。
代碼實現

def knapsack_multi(weights, values, counts, C):n = len(weights)dp = [0] * (C + 1)for i in range(n):weight, value, count = weights[i], values[i], counts[i]# 二進制拆分k = 1while k <= count:# 0-1背包處理拆分后的物品for j in range(C, k * weight - 1, -1):dp[j] = max(dp[j], dp[j - k * weight] + k * value)count -= kk *= 2# 處理剩余物品if count > 0:for j in range(C, count * weight - 1, -1):dp[j] = max(dp[j], dp[j - count * weight] + count * value)return dp[C]

3.5 二維費用背包問題

問題描述：
選擇物品除了重量限制外，還有第二個維度的費用限制（如體積）。
狀態定義：
dp[i][j][k]表示前i個物品，在重量不超過j且體積不超過k的情況下的最大價值。
狀態轉移方程：

dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-w[i]][k-v[i]] + value[i]  # 前提是j >= w[i]且k >= v[i])

一維數組優化

for i in range(n):for j in range(C, w[i]-1, -1):  # 重量維度逆序for k in range(D, v[i]-1, -1):  # 體積維度逆序dp[j][k] = max(dp[j][k], dp[j-w[i]][k-v[i]] + value[i])

3.6 分組背包問題

問題描述：
物品被分成若干組，每組內的物品互斥，最多只能選一個。
狀態轉移方程：

dp[k][j] = max(dp[k-1][j], max(dp[k-1][j-w[i]] + v[i] for i in group[k]))

代碼實現

def knapsack_group(groups, weights, values, C):n = len(groups)  # 組數dp = [0] * (C + 1)for k in range(n):for j in range(C, -1, -1):  # 逆序遍歷容量for i in groups[k]:  # 遍歷組內物品if j >= weights[i]:dp[j] = max(dp[j], dp[j - weights[i]] + values[i])return dp[C]

3.7 背包問題變種總結

問題類型	核心區別	狀態轉移關鍵
0-1 背包	每個物品選 0 或 1 次	逆序遍歷容量
完全背包	每個物品可重復選	正序遍歷容量
多重背包	每個物品有數量限制	二進制拆分后轉為 0-1 背包
二維費用背包	增加第二個費用維度	增加一維狀態
分組背包	物品分組，每組最多選一個	組間順序遍歷，組內逆序遍歷容量

3.8 解題步驟建議

明確問題類型：判斷是 0-1 背包、完全背包還是其他變種。
定義狀態：通常dp[i][j]表示前i個物品在容量j下的最優解。
推導轉移方程：根據物品選取規則確定狀態轉移方式。
處理邊界條件：初始化dp[0][j]和dp[i][0]。
優化空間：若狀態轉移僅依賴上一行，考慮用一維數組優化。

3.9 LeetCode 相關題目

Leetcode 416. 分割等和子集（0-1 背包）
目標：判斷能否將數組分割成兩個子集，使得它們的和相等。
提示：轉化為背包問題，容量為總和的一半。
Leetcode 322. 零錢兌換（完全背包）
目標：用最少的硬幣湊成目標金額。
提示：狀態定義為dp[i]表示湊成金額i所需的最少硬幣數。
Leetcode 474. 一和零（二維費用背包）
目標：用最多的m個 0 和n個 1 組成最多的字符串。
提示：每個字符串的 0 和 1 數量作為兩個費用維度。
Leetcode 1155. 擲骰子的 N 種方法（分組背包）
目標：計算擲d個骰子，每個骰子有f個面，得到目標和的方法數。
提示：每個骰子作為一組，組內選擇一個面。

通過掌握背包問題的基本模型和優化方法，可以解決許多資源分配類的動態規劃問題。關鍵在于準確識別問題類型，并靈活調整狀態定義和轉移方程。

四、其他動態規劃問題

4.1 編輯距離問題（LeetCode 72）

問題描述

給定兩個單詞 word1 和 word2 ，計算出將 word1 轉換成 word2 所使用的最少操作數。可以進行的操作有插入一個字符、刪除一個字符、替換一個字符。

狀態定義

設 dp[i][j] 表示將 word1 的前 i 個字符轉換為 word2 的前 j 個字符所需的最少操作數。

狀態轉移方程

當 i = 0 時，dp[0][j] = j，表示將空字符串轉換為 word2 的前 j 個字符，需要插入 j 個字符。
當 j = 0 時，dp[i][0] = i，表示將 word1 的前 i 個字符轉換為空字符串，需要刪除 i 個字符。
當 word1[i - 1] == word2[j - 1] 時，dp[i][j] = dp[i - 1][j - 1]，此時不需要進行額外操作。
當 word1[i - 1] != word2[j - 1] 時，dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1) ，分別對應替換、刪除、插入操作。

代碼實現

def minDistance(word1, word2):m, n = len(word1), len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(m + 1):dp[i][0] = ifor j in range(n + 1):dp[0][j] = jfor i in range(1, m + 1):for j in range(1, n + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1return dp[m][n]

4.2 最長公共子序列問題（LeetCode 1143）

問題描述

給定兩個字符串 text1 和 text2 ，返回這兩個字符串的最長公共子序列的長度。子序列是一個可以由另一個序列刪除一些元素（也可以不刪除）但不改變剩余元素順序得到的新序列。

狀態定義

設 dp[i][j] 表示 text1 的前 i 個字符和 text2 的前 j 個字符的最長公共子序列的長度。

狀態轉移方程

當 i = 0 或 j = 0 時，dp[i][j] = 0，因為至少有一個字符串為空，最長公共子序列長度為 0。
當 text1[i - 1] == text2[j - 1] 時，dp[i][j] = dp[i - 1][j - 1] + 1 。
當 text1[i - 1] != text2[j - 1] 時，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。

代碼實現

def longestCommonSubsequence(text1, text2):m, n = len(text1), len(text2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):if text1[i - 1] == text2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]

4.3 最大子序和問題（LeetCode 53）

問題描述

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

狀態定義

設 dp[i] 表示以 nums[i] 結尾的連續子數組的最大和。

狀態轉移方程

dp[i] = max(dp[i - 1] + nums[i], nums[i]) ，即要么將當前元素加入到前面的子數組中，要么以當前元素作為新的子數組開始。

代碼實現

def maxSubArray(nums):n = len(nums)dp = [0] * ndp[0] = nums[0]result = dp[0]for i in range(1, n):dp[i] = max(dp[i - 1] + nums[i], nums[i])result = max(result, dp[i])return result

其實本題從動態規劃的角度來看只依賴dp[i-1]，即上一個狀態，也可以從貪心算法角度理解。每一步計算當前累積和，如果當前累積和小于0，不如直接從當前位置開始再次累積。并在每步存儲當前計算得到的最大子序和。

4.4 最長上升子序列（LIS）問題

問題描述

給定一個無序的整數數組，找到其中最長上升子序列的長度。子序列是一個可以由另一個序列刪除一些元素（也可以不刪除）但不改變剩余元素順序得到的新序列。

狀態定義
設 dp[i] 表示以 nums[i] 結尾的最長上升子序列的長度。

狀態轉移方程

初始化：dp[i] = 1 ，因為每個元素自身都可以構成一個長度為 1 的上升子序列。
對于 i > 0 ，遍歷 0 到 i - 1 的元素，如果 nums[j] < nums[i] ，則 dp[i] = max(dp[i], dp[j] + 1) ，表示如果能找到前面比當前元素小的元素，就可以將當前元素接到其對應的最長上升子序列后面，更新當前位置的最長上升子序列長度。
當前狀態依賴前面所有狀態，可以想象，在狀態轉移圖中任何一個狀態可以轉到之后的狀態（對比馬爾可夫性質，當前狀態只依賴前一個狀態）。

代碼實現

def lengthOfLIS(nums):n = len(nums)dp = [1] * nfor i in range(n):for j in range(i):if nums[j] < nums[i]:dp[i] = max(dp[i], dp[j] + 1)return max(dp) if dp else 0

4.5 硬幣找零 - 最少硬幣數（另一種視角）

問題描述

給定不同面額的硬幣數組 coins 和一個總金額 amount ，計算湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

狀態定義

設 dp[i] 表示湊成金額 i 所需的最少硬幣個數。

狀態轉移方程

初始化：dp[0] = 0 ，表示湊成金額 0 需要 0 個硬幣；對于其他金額 i ，初始化為一個較大的值（如 amount + 1 ），方便后續取最小值比較。
對于每個金額 i ，遍歷所有硬幣面額 coin ，如果 i >= coin ，則 dp[i] = min(dp[i], dp[i - coin] + 1) ，表示在能使用該硬幣的情況下，取使用該硬幣和不使用該硬幣時的較小硬幣數。

代碼實現

def coinChange(coins, amount):dp = [amount + 1] * (amount + 1)dp[0] = 0for i in range(1, amount + 1):for coin in coins:if i >= coin:dp[i] = min(dp[i], dp[i - coin] + 1)return dp[amount] if dp[amount] != amount + 1 else -1

類似完全背包問題，不同的是背包問題容量限制是不超過即可，本題硬幣找零需要恰好滿足。

4.6 分割等和之集

問題描述

給定一個只包含正整數的非空數組 nums 。判斷能否將這個數組分割成兩個子集，使得兩個子集的元素和相等。

解題思路

這道題可以轉化為 0 - 1 背包問題。

目標轉換：要使數組能分割成兩個元素和相等的子集，那么數組所有元素的和 sum(nums) 必須是偶數（因為兩個子集和相等，總和必然能被 2 整除），然后問題就變為能否從數組中選取一些元素，使得它們的和等于 sum(nums) / 2 。
類比背包：可以把 sum(nums) / 2 看作背包的容量，數組中的每個元素 nums[i] 看作物品的重量，同時也是物品的價值（因為選取了這個元素，就得到了它對應的價值，且重量就是它本身的值），判斷是否能裝滿背包（即是否能找到元素和等于 sum(nums) / 2 的子集）。

狀態定義

設 dp[i][j] 表示從數組的前 i 個元素中選取一些元素，能否使它們的和等于 j 。如果能，dp[i][j] 為 True ，否則為 False 。

狀態轉移方程

不選第 i 個元素：如果前 i - 1 個元素已經能組成和為 j ，那么不選第 i 個元素也能滿足，即 dp[i][j] = dp[i - 1][j] 。
選第 i 個元素：前提是 j >= nums[i - 1] （因為數組下標從 0 開始，這里 nums[i - 1] 表示第 i 個元素），此時如果前 i - 1 個元素能組成和為 j - nums[i - 1] ，那么選上第 i 個元素就能組成和為 j ，即 dp[i][j] = dp[i - 1][j - nums[i - 1]] 。
綜合起來，狀態轉移方程為：
- 當 j < nums[i - 1] 時，dp[i][j] = dp[i - 1][j]；
- 當 j >= nums[i - 1] 時，dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]] 。

初始條件

dp[0][0] = True ，表示沒有元素時，和為 0 是可以實現的。
對于 j > 0 ，dp[0][j] = False ，因為沒有元素時，無法組成大于 0 的和。

代碼實現

def canPartition(nums):total = sum(nums)if total % 2 != 0:return Falsetarget = total // 2dp = [False] * (target + 1)dp[0] = Truefor num in nums:for j in range(target, num - 1, -1):dp[j] = dp[j] or dp[j - num]return dp[target]