動態規劃練習題

題目描述

給定兩個字符串 text1 和 text2，要求返回這兩個字符串的最長公共子序列。例如對于字符串 “ABAZDC” 和 “BACBAD”，需找出它們最長的公共子序列。子序列是指在不改變其余字符相對位置的情況下，從原始字符串中刪除某些字符（也可以不刪除）后形成的新字符串。

最優解（Python）

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]

解析

1. 動態規劃思路：本題采用動態規劃方法，核心是通過分析子問題的解來構建最終問題的解。
2. 狀態定義：定義二維數組 dp[i][j] 表示 text1 的前 i 個字符和 text2 的前 j 個字符的最長公共子序列長度。
3. 狀態轉移方程：
   • 當 text1[i - 1] == text2[j - 1] 時，說明當前字符相等，此時 dp[i][j] 等于 dp[i - 1][j - 1] + 1 ，即在前 i - 1 和前 j - 1 個字符最長公共子序列基礎上長度加1。
   • 當 text1[i - 1] != text2[j - 1] 時，dp[i][j] 取 dp[i - 1][j] 和 dp[i][j - 1] 中的較大值，因為此時最長公共子序列要么是 text1 前 i - 1 個字符與 text2 前 j 個字符的最長公共子序列，要么是 text1 前 i 個字符與 text2 前 j - 1 個字符的最長公共子序列。
4. 邊界條件：dp[0][j] = 0 表示 text1 為空字符串時，最長公共子序列長度為0；dp[i][0] = 0 表示 text2 為空字符串時，最長公共子序列長度為0 。
5. 時間復雜度：由于使用了兩層嵌套循環遍歷兩個字符串，時間復雜度為 $O(m\times n)$，其中 $m$ 和 $n$ 分別是 text1 和 text2 的長度。
6. 空間復雜度：使用了一個二維數組 dp 存儲中間結果，空間復雜度為 $O(m\times n)$ ，不過可以通過滾動數組優化為 $O(min(m,n))$ 。

題目描述

題目鏈接為https://leetcode-cn.com/problems/climbing-stairs/description/ ，假設你正在爬樓梯，需要 n 階才能到達樓頂。每次你可以爬 1 或 2 個臺階，要求計算有多少種不同的方法可以爬到樓頂 。其中，n 是一個正整數，且滿足 1 <= n <= 45 。例如：

• 當輸入 n = 2 時，輸出為 2，因為有兩種方法可以爬到樓頂，分別是 “1 階 + 1 階” 和 “2 階” 。
• 當輸入 n = 3 時，輸出為 3，因為有三種方法可以爬到樓頂，分別是 “1 階 + 1 階 + 1 階” 、“1 階 + 2 階” 、“2 階 + 1 階” 。

最優解（Python）

def climbStairs(n):if n <= 2:return na, b = 1, 2for _ in range(2, n):a, b = b, a + breturn b

解析

1. 動態規劃思路：本題可采用動態規劃的方法求解。動態規劃的核心是將原問題分解為多個子問題，通過求解子問題并保存結果來避免重復計算，最終得到原問題的解。
2. 狀態定義：定義 f(n) 表示爬到第 n 階樓梯的不同方法數。
3. 狀態轉移方程：因為每次可以爬 1 階或 2 階，所以爬到第 n 階的方法數等于爬到第 n - 1 階的方法數加上爬到第 n - 2 階的方法數，即 f(n) = f(n - 1) + f(n - 2) 。這是一個類似斐波那契數列的遞推關系。
4. 邊界條件：當 n = 1 時，只有一種方法（爬 1 階），即 f(1) = 1 ；當 n = 2 時，有兩種方法（兩次爬 1 階或一次爬 2 階） ，即 f(2) = 2 。
5. 代碼實現細節：代碼中使用了兩個變量 a 和 b 分別表示 f(n - 2) 和 f(n - 1) ，通過不斷更新這兩個變量來計算 f(n) 。循環從 n = 2 開始，每次迭代更新 a 和 b 的值，最終 b 存儲的就是爬到第 n 階的方法數。
6. 復雜度分析：
   • 時間復雜度：代碼中只進行了一次循環，循環次數為 n - 2 次，每次循環的操作都是常數時間的，所以時間復雜度為 $O(n)$ 。
   • 空間復雜度：只使用了常數個額外變量（a 和 b ），所以空間復雜度為 $O(1)$ 。 這種空間復雜度為常數的實現方式是對動態規劃空間優化后的結果，相較于使用數組存儲所有子問題結果（空間復雜度為 $O(n)$ ）更為高效。

題目描述

題目鏈接為https://leetcode-cn.com/problems/triangle/description/ ，給定一個三角形 triangle ，它是一個二維列表，其中 triangle[i] 表示三角形第 i 行的數字列表。要求找到從三角形頂部到底部的最小路徑和。在每一步只能移動到下一行中相鄰的節點上。例如，對于三角形 [[2],[3,4],[6,5,7],[4,1,8,3]] ，從頂部到底部的最小路徑和是 11（路徑為 2→3→5→1 ）。

最優解（Python）

def minimumTotal(triangle):n = len(triangle)# 從倒數第二行開始向上遍歷for i in range(n - 2, -1, -1):for j in range(len(triangle[i])):# 狀態轉移：選擇下方相鄰兩個數中較小的，加上當前數triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])return triangle[0][0]

解析

1. 動態規劃思路：采用動態規劃來解決此問題。動態規劃的關鍵在于將問題分解為多個子問題，并利用子問題的解來構建最終問題的解。
2. 狀態定義：把 triangle[i][j] 看作狀態，表示從三角形第 i 行第 j 列這個位置到底部的最小路徑和。
3. 狀態轉移方程：對于第 i 行第 j 列的元素，它下一步可以移動到下一行的第 j 列或者第 j + 1 列。所以 triangle[i][j] 的最小路徑和等于當前位置的值加上下一行相鄰兩個位置中較小的那個位置的最小路徑和，即 triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]) 。
4. 遍歷順序：從三角形的倒數第二行開始向上遍歷，因為最底層的元素到底部的最小路徑和就是其自身的值，以此為基礎向上遞推。
5. 邊界條件：最底層的元素不需要進行額外計算，其自身值就是從它到底部的最小路徑和（因為已經是最底層了）。
6. 復雜度分析：
   • 時間復雜度：使用了兩層嵌套循環，外層循環遍歷行數，內層循環遍歷每行的元素，總的時間復雜度為 $O(n^2)$ ，其中 $n$ 是三角形的行數。
   • 空間復雜度：直接在原三角形數組上進行操作，沒有使用額外的與問題規模相關的空間，所以空間復雜度為 $O(1)$ 。 這種在原數據結構上直接修改來保存中間結果的方式，有效避免了額外的空間開銷。

題目描述

鏈接：https://leetcode-cn.com/problems/maximum-subarray/ 。

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。例如，輸入 nums = [-2,1,-3,4,-1,2,1,-5,4] ，輸出為 6 ，因為連續子數組 [4,-1,2,1] 的和最大，為 6 。

最優解（Python）

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

解析

1. 動態規劃思路：本題運用動態規劃方法。動態規劃的核心是將復雜問題分解為多個相互關聯的子問題，通過求解子問題并保存結果，避免重復計算，從而高效地解決原問題。
2. 狀態定義：定義 dp[i] 表示以 nums[i] 結尾的連續子數組的最大和 。
3. 狀態轉移方程：對于 dp[i] ，它有兩種情況。一種是只取 nums[i] 這一個元素作為子數組，另一種是將 nums[i] 加入到以 nums[i - 1] 結尾的連續子數組中。所以狀態轉移方程為 dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
4. 邊界條件：當 i = 0 時，dp[0] = nums[0] ，因為此時以 nums[0] 結尾的連續子數組就是它本身。
5. 求解過程：在循環中，每計算出一個 dp[i] ，就更新 max_sum ，max_sum 記錄的是到當前位置為止，所有以不同元素結尾的連續子數組中的最大和。
6. 復雜度分析：
   • 時間復雜度：代碼中只有一層循環，循環次數為數組的長度 n ，每次循環內的操作都是常數時間的，所以時間復雜度為 $O(n)$ 。
   • 空間復雜度：使用了一個長度為 n 的數組 dp 來保存中間結果，所以空間復雜度為 $O(n)$ 。不過，還可以進一步優化，將空間復雜度降為 $O(1)$ ，即不使用 dp 數組，而是用一個變量來記錄以當前元素結尾的最大子數組和。優化后的代碼如下：

def maxSubArray(nums):n = len(nums)if n == 0:return 0cur_sum = nums[0]max_sum = nums[0]for i in range(1, n):cur_sum = max(nums[i], cur_sum + nums[i])max_sum = max(max_sum, cur_sum)return max_sum

此時，只使用了幾個額外的變量，空間復雜度為 $O(1)$ 。

題目描述（另一題，鏈接：https://leetcode-cn.com/problems/maximum-product-subarray/description/ ）

給定一個整數數組 nums ，找出一個乘積最大的連續子數組。子數組最少包含一個元素。例如，輸入 nums = [2,3,-2,4] ，輸出為 6 ，因為子數組 [2,3] 有最大乘積 6 。

最優解（Python）

def maxProduct(nums):n = len(nums)if n == 0:return 0max_ending_here = min_ending_here = res = nums[0]for i in range(1, n):# 暫存當前的最大值，用于計算新的最小值temp_max = max_ending_heremax_ending_here = max(nums[i], max_ending_here * nums[i], min_ending_here * nums[i])min_ending_here = min(nums[i], temp_max * nums[i], min_ending_here * nums[i])res = max(res, max_ending_here)return res

解析

1. 動態規劃思路：同樣采用動態規劃策略。由于數組中存在負數，負數與負數相乘可能得到更大的乘積，所以不能簡單地用與最大子數組和類似的方法。需要同時記錄以當前元素結尾的最大乘積子數組和最小乘積子數組。
2. 狀態定義：定義 max_ending_here 表示以當前元素 nums[i] 結尾的最大乘積子數組的乘積，min_ending_here 表示以當前元素 nums[i] 結尾的最小乘積子數組的乘積 。
3. 狀態轉移方程：
   • 對于 max_ending_here ，它的取值可能是當前元素 nums[i] ，也可能是當前元素與之前的 max_ending_here 相乘，還可能是當前元素與之前的 min_ending_here 相乘（因為負負得正，可能得到更大的值），即 max_ending_here = max(nums[i], max_ending_here * nums[i], min_ending_here * nums[i]) 。
   • 對于 min_ending_here ，它的取值可能是當前元素 nums[i] ，也可能是當前元素與之前的 max_ending_here 相乘（得到較小的值），還可能是當前元素與之前的 min_ending_here 相乘，即 min_ending_here = min(nums[i], temp_max * nums[i], min_ending_here * nums[i]) 。這里的 temp_max 是暫存的上一輪的 max_ending_here ，用于計算新的 min_ending_here 。
4. 邊界條件：當 i = 0 時，max_ending_here = min_ending_here = nums[0] 。
5. 求解過程：在循環中，每次更新 max_ending_here 和 min_ending_here 后，都用 res 記錄到當前位置為止的最大乘積，最后返回 res 。
6. 復雜度分析：
   • 時間復雜度：只有一層循環，循環次數為數組長度 n ，每次循環內操作是常數時間，所以時間復雜度為 $O(n)$ 。
   • 空間復雜度：只使用了幾個額外變量，空間復雜度為 $O(1)$ 。

題目描述

題目鏈接為https://leetcode-cn.com/problems/coin-change/description/ 。給定不同面額的硬幣 coins 列表和一個總金額 amount ，編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。假設每種硬幣的數量是無限的。例如：

• 輸入 coins = [1, 2, 5] ，amount = 11 ，輸出為 3 ，因為 11 = 5 + 5 + 1 ，最少需要 3 枚硬幣。
• 輸入 coins = [2] ，amount = 3 ，輸出為 -1 ，因為無法用面額為 2 的硬幣湊出金額 3 。

最優解（Python）

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

解析

1. 動態規劃思路：本題使用動態規劃來解決。動態規劃的核心在于將問題分解為多個子問題，通過求解子問題并保存結果，避免重復計算，最終得到原問題的解。
2. 狀態定義：定義 dp[i] 表示湊成金額 i 所需的最少硬幣個數。
3. 狀態轉移方程：對于金額 i ，遍歷所有硬幣面額 coin ，如果 coin <= i ，那么 dp[i] 可以由 dp[i - coin] + 1 得到（dp[i - coin] 是湊成金額 i - coin 所需的最少硬幣個數，加上一枚面額為 coin 的硬幣就可以湊成金額 i ），并且取 dp[i] 和 dp[i - coin] + 1 中的較小值，即 dp[i] = min(dp[i], dp[i - coin] + 1) 。
4. 邊界條件：dp[0] = 0 ，表示湊成金額 0 不需要任何硬幣。初始化 dp 數組其他元素為 amount + 1 ，這是一個不可能達到的較大值，用于后續比較更新。
5. 求解過程：通過兩層循環，外層循環遍歷從 1 到 amount 的所有金額，內層循環遍歷所有硬幣面額，不斷更新 dp 數組。最后，如果 dp[amount] 仍然是初始的 amount + 1 ，說明無法湊出該金額，返回 -1 ；否則返回 dp[amount] 。
6. 復雜度分析：
   • 時間復雜度：有兩層循環，外層循環次數為 amount 次，內層循環次數為硬幣種類數（假設為 m ），所以時間復雜度為 $O(m\times amount)$ 。
   • 空間復雜度：使用了一個長度為 amount + 1 的數組 dp 來保存中間結果，所以空間復雜度為 $O(amount)$ 。