練習題
題目描述
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組 nums，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
示例 1：
輸入：nums = [1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3），偷竊到的最高金額 = 1 + 3 = 4 。
示例 2：
輸入：nums = [2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋（金額 = 2），偷竊 3 號房屋（金額 = 9），接著偷竊 5 號房屋（金額 = 1），偷竊到的最高金額 = 2 + 9 + 1 = 12 。
最優解（動態規劃 + 空間優化）
利用動態規劃思想，通過滾動變量優化空間復雜度至 (O(1))。
思路：
定義兩個變量 first 和 second，分別表示偷到前前一間房屋和前一間房屋的最大金額。對于當前房屋，有兩種選擇：
- 偷當前房屋：則總金額為
first + 當前房屋金額。 - 不偷當前房屋：則總金額為
second。
取兩者最大值更新狀態，逐步迭代。
代碼：
class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums) == 1: return nums[0] first, second = nums[0], max(nums[0], nums[1]) for i in range(2, len(nums)): first, second = second, max(second, first + nums[i]) return second
復雜度分析：
- 時間復雜度：(O(n))，其中 (n) 是房屋數量，需遍歷數組一次。
- 空間復雜度：(O(1))，僅用兩個變量存儲狀態。
答案解析：
- 初始化
first為第一間房屋金額，second為前兩間房屋的較大值。 - 從第三間房屋開始迭代，每次更新
first和second，first代表前前一間的最大值，second代表前一間的最大值。 - 最終
second即為偷到最后一間房屋時的最大金額，返回該值。
題目：完全平方數
給定正整數 ( n )，找到若干個完全平方數（比如 ( 1, 4, 9, 16, \dots )）使得它們的和等于 ( n )，要求組成和的完全平方數的個數最少。
解法：動態規劃
思路：
定義 ( dp[i] ) 表示組成 ( i ) 的最少完全平方數個數。對于每個 ( i )，遍歷小于 ( i ) 的完全平方數 ( j^2 )，通過狀態轉移方程 ( dp[i] = \min(dp[i], dp[i - j^2] + 1) ) 計算最小值。
代碼：
import mathdef numSquares(n):dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1):max_j = int(math.sqrt(i))for j in range(1, max_j + 1):if i >= j * j:dp[i] = min(dp[i], dp[i - j * j] + 1)return dp[n]
解釋：
- 初始化 ( dp ) 數組，
dp[0] = 0表示 ( 0 ) 不需要任何完全平方數。 - 遍歷 ( i ) 從 ( 1 ) 到 ( n )，對于每個 ( i )，遍歷 ( j )（( j^2 \leq i )）。
- 通過狀態轉移方程更新 ( dp[i] )，取最小值。
- 最終 ( dp[n] ) 即為組成 ( n ) 的最少完全平方數個數。
時間復雜度：( O(n\sqrt{n}) )，遍歷 ( n ) 次，每次遍歷 ( \sqrt{n} ) 次。
空間復雜度：( O(n) )，存儲 ( dp ) 數組。
此方法通過動態規劃高效地計算出最少完全平方數個數，確保了算法的正確性和效率。
題目描述
給你兩個單詞 word1 和 word2，請返回將 word1 轉換成 word2 所使用的最少操作數。你可以對一個單詞進行如下三種操作：
- 插入一個字符
- 刪除一個字符
- 替換一個字符
最優解（Python）
from typing import Listclass Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)# 創建二維數組，dp[i][j]表示將 word1 的前 i 個字符轉換為 word2 的前 j 個字符的最少操作數dp = [[0] * (n + 1) for _ in range(m + 1)]# 初始化邊界條件for i in range(m + 1):dp[i][0] = i # word1 前 i 個字符轉換為空字符串，需要刪除 i 個字符for j in range(n + 1):dp[0][j] = j # 空字符串轉換為 word2 前 j 個字符，需要插入 j 個字符# 填充 dp 數組for 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:# 取插入、刪除、替換三種操作的最小值，然后加 1（因為進行了一次操作）dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])return dp[m][n]
最優解分析
-
動態規劃思路：
- 定義
dp[i][j]表示將word1的前i個字符轉換為word2的前j個字符的最少操作數。 - 邊界條件：
- 若
word1為空字符串（i = 0），則需要插入j個字符才能轉換為word2的前j個字符，即dp[0][j] = j。 - 若
word2為空字符串（j = 0），則需要刪除i個字符才能將word1的前i個字符轉換為空字符串，即dp[i][0] = i。
- 若
- 狀態轉移方程：
- 當
word1[i - 1] == word2[j - 1]時，當前字符相同，不需要進行插入、刪除或替換操作，所以dp[i][j] = dp[i - 1][j - 1]。 - 當
word1[i - 1] != word2[j - 1]時，有三種操作選擇：- 插入：將
word1的前i個字符轉換為word2的前j - 1個字符（dp[i][j - 1]），再插入一個字符，操作數為dp[i][j - 1] + 1。 - 刪除：將
word1的前i - 1個字符轉換為word2的前j個字符（dp[i - 1][j]），再刪除一個字符，操作數為dp[i - 1][j] + 1。 - 替換：將
word1的前i - 1個字符轉換為word2的前j - 1個字符（dp[i - 1][j - 1]），再替換一個字符，操作數為dp[i - 1][j - 1] + 1。
取這三種操作數的最小值，即dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])。
- 插入：將
- 當
- 定義
-
復雜度分析：
- 時間復雜度：( O(m \times n) )，其中 ( m ) 和 ( n ) 分別是
word1和word2的長度，需要遍歷一個 ( (m + 1) \times (n + 1) ) 的二維數組。 - 空間復雜度：( O(m \times n) )，使用了一個 ( (m + 1) \times (n + 1) ) 的二維數組來存儲中間狀態。
- 時間復雜度：( O(m \times n) )，其中 ( m ) 和 ( n ) 分別是
編輯距離（最少操作數轉換單詞）
題目描述
給定兩個單詞 word1 和 word2，計算將 word1 轉換成 word2 所需的最少操作數。允許的操作有三種：
- 插入一個字符
- 刪除一個字符
- 替換一個字符
最優解：動態規劃（Python實現）
from typing import Listclass Solution:def minDistance(self, word1: str, word2: str) -> int:m, n = len(word1), len(word2)# 創建二維數組 dp，其中 dp[i][j] 表示將 word1 的前 i 個字符轉換為 word2 的前 j 個字符的最少操作數dp = [[0] * (n + 1) for _ in range(m + 1)]# 初始化邊界條件：當其中一個單詞為空時的操作數for i in range(m + 1):dp[i][0] = i # 刪除 word1 前 i 個字符（全部刪除，操作數為 i）for j in range(n + 1):dp[0][j] = j # 插入 word2 前 j 個字符（全部插入，操作數為 j）# 填充 dp 數組for 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:# 當前字符不同，選擇三種操作中的最小值并加 1（當前操作）dp[i][j] = 1 + min(dp[i-1][j], # 刪除 word1 的第 i 個字符（對應 word1 前 i-1 轉換為 word2 前 j）dp[i][j-1], # 插入 word2 的第 j 個字符（對應 word1 前 i 轉換為 word2 前 j-1）dp[i-1][j-1] # 替換 word1 的第 i 個字符為 word2 的第 j 個字符（對應前 i-1 和 j-1 轉換）)return dp[m][n] # 返回最終結果，即兩個完整單詞的最少操作數
最優解分析
1. 動態規劃思路
編輯距離問題是典型的動態規劃問題，核心是通過子問題的解推導原問題的解。
- 狀態定義：
設dp[i][j]表示將word1的前i個字符轉換為word2的前j個字符所需的最少操作數。 - 狀態轉移：
- 若當前字符相同（
word1[i-1] == word2[j-1]），則無需操作，直接繼承左上角的狀態dp[i-1][j-1]。 - 若當前字符不同，則有三種操作選擇，取其中最小值并加 1（當前操作）：
- 刪除：刪除
word1的第i個字符，操作數為dp[i-1][j] + 1。 - 插入：在
word1中插入word2的第j個字符，操作數為dp[i][j-1] + 1。 - 替換：將
word1的第i個字符替換為word2的第j個字符，操作數為dp[i-1][j-1] + 1。
- 刪除：刪除
- 若當前字符相同（
2. 邊界條件
- 當
word1為空（i=0）時，需要插入word2的前j個字符，操作數為j。 - 當
word2為空（j=0）時，需要刪除word1的前i個字符，操作數為i。
3. 復雜度分析
- 時間復雜度：( O(m \times n) )，其中
m和n分別為兩個單詞的長度。需要遍歷一個 ( (m+1) \times (n+1) ) 的二維數組。 - 空間復雜度：( O(m \times n) )，使用二維數組存儲中間狀態。若優化空間，可壓縮為一維數組（每次僅保留前一行的狀態），但此處采用直觀的二維數組解法，便于理解。
4. 示例推導
以 word1 = "horse", word2 = "ros" 為例：
- 初始化邊界：第一行和第一列分別為
0,1,2,3和0,1,2,3,4,5（對應插入或刪除操作）。 - 填充過程中，當字符相同時（如
hvsr不同，ovso相同），根據狀態轉移方程逐步計算每個dp[i][j]。 - 最終
dp[5][3]即為結果3（實際最少操作：horse→rorse（替換 h→r）→rose（刪除 r）→ros（刪除 e），共 3 步）。
總結
編輯距離問題通過動態規劃將復雜的字符串轉換問題分解為子問題，利用狀態轉移方程高效求解。關鍵在于正確定義狀態和轉移邏輯，邊界條件的處理也至關重要。該解法是此類問題的經典解法，時間和空間復雜度均為多項式級別，適用于大多數實際場景。
題目描述
給定一個非負整數數組 nums，你最初位于數組的 第一個下標。數組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最后一個下標。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步到下標 1，然后跳 3 步到達最后一個下標。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置（值為 0），無法繼續跳躍到最后一個下標。
最優解（貪心算法）
通過維護當前能到達的最遠位置，遍歷數組時不斷更新該位置，若在遍歷過程中最遠位置覆蓋最后一個下標，則返回 True；若當前位置超過最遠位置，說明無法繼續跳躍，返回 False。
Python代碼
from typing import Listclass Solution:def canJump(self, nums: List[int]) -> bool:n = len(nums)max_reach = 0 # 初始化當前能到達的最遠位置for i in range(n):# 如果當前位置在可到達范圍內，則嘗試更新最遠位置if i <= max_reach:max_reach = max(max_reach, i + nums[i])# 提前判斷是否已到達或超過最后一個下標，優化性能if max_reach >= n - 1:return Trueelse:# 當前位置超出可到達范圍，無法繼續跳躍break# 遍歷結束后，若最遠位置仍未到達最后一個下標，返回Falsereturn max_reach >= n - 1
最優解分析
思路解析
-
貪心策略：
每次遍歷到位置i時，若i在當前最遠可達位置max_reach內，則更新max_reach為i + nums[i]（即從i出發能到達的最遠位置）和當前max_reach中的較大值。- 若
max_reach在遍歷過程中已覆蓋最后一個下標（n-1），則直接返回True，無需繼續遍歷。 - 若某一位置
i超出max_reach，說明后續位置無法到達，直接跳出循環并返回False。
- 若
-
邊界處理：
- 當數組長度為
0或1時，直接返回True（空數組題目保證輸入合法，長度為 1 時無需跳躍即可到達）。 - 遍歷過程中，若
i超過max_reach，說明中間存在無法跨越的“斷層”，直接終止遍歷。
- 當數組長度為
復雜度分析
- 時間復雜度：( O(n) )，其中 ( n ) 是數組
nums的長度。僅需遍歷數組一次，每個元素處理時間為常數。 - 空間復雜度：( O(1) )，僅使用常數級額外空間（
max_reach和循環變量）。
示例推導
以示例 2 nums = [3,2,1,0,4] 為例：
- 初始
max_reach = 0。 i=0：0 <= 0，更新max_reach = max(0, 0+3=3)，此時max_reach=3，未達最后下標（4）。i=1：1 <= 3，更新max_reach = max(3, 1+2=3)，仍為 3。i=2：2 <= 3，更新max_reach = max(3, 2+1=3)，仍為 3。i=3：3 <= 3，更新max_reach = max(3, 3+0=3)，仍為 3。i=4：4 > 3，跳出循環，返回False，符合預期。
關鍵點
- 貪心的核心：每次盡可能擴展最遠可達范圍，避免重復計算中間狀態。
- 提前終止：一旦最遠可達范圍覆蓋最后一個下標，立即返回
True，優化最壞情況下的性能。
該解法通過線性遍歷和常數空間，高效解決了跳躍游戲問題，是此類問題的經典貪心解法。
題目描述
給定一個非負整數數組 nums，你最初位于數組的 第一個下標。數組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最后一個下標。
最優解（貪心算法）
通過維護當前能到達的最遠位置，遍歷數組時動態更新該位置，若在遍歷過程中最遠位置覆蓋最后一個下標，則直接返回 True；若當前位置超出最遠可達范圍，說明無法繼續跳躍，返回 False。
Python代碼
from typing import Listclass Solution:def canJump(self, nums: List[int]) -> bool:n = len(nums)max_reach = 0 # 當前能到達的最遠下標for i in range(n):# 如果當前位置在可達范圍內，則嘗試更新最遠可達位置if i <= max_reach:max_reach = max(max_reach, i + nums[i])# 提前判斷是否已到達終點，優化性能if max_reach >= n - 1:return Trueelse:# 當前位置不可達，后續位置也無法到達break# 遍歷結束后，檢查最遠可達位置是否覆蓋終點return max_reach >= n - 1
最優解分析
核心思路：貪心策略
-
維護最遠可達位置：
用max_reach表示從起點出發，經過一系列跳躍后能到達的最遠下標。初始時max_reach = 0（起點位置）。- 遍歷每個下標
i，若i在max_reach范圍內（即i <= max_reach），說明可以從前面的某個位置跳躍到i，此時更新max_reach為i + nums[i]（從i出發能跳到的最遠位置）和當前max_reach中的較大值。 - 若
i超出max_reach（即i > max_reach），說明無法到達i，后續下標也無法到達，直接終止遍歷。
- 遍歷每個下標
-
提前終止條件：
一旦max_reach覆蓋最后一個下標（n - 1），立即返回True，無需遍歷剩余元素，優化最壞情況下的時間復雜度。
復雜度分析
- 時間復雜度：( O(n) )，其中 ( n ) 是數組長度。每個元素僅遍歷一次，每次操作均為常數時間。
- 空間復雜度：( O(1) )，僅使用常數級額外空間（
max_reach和循環變量）。
示例推導
-
示例 1：
nums = [2, 3, 1, 1, 4]i=0：0 <= 0，max_reach = max(0, 0+2=2)→2（未達終點，繼續）。i=1：1 <= 2，max_reach = max(2, 1+3=4)→4（已達終點4，返回True）。
-
示例 2：
nums = [3, 2, 1, 0, 4]i=0：0 <= 0，max_reach = 3。i=1：1 <= 3，max_reach = 3（1+2=3）。i=2：2 <= 3，max_reach = 3（2+1=3）。i=3：3 <= 3，max_reach = 3（3+0=3）。i=4：4 > 3，跳出循環，返回False。
關鍵點
- 貪心的本質：每次盡可能擴展可達范圍，避免回溯或重復計算，確保線性時間復雜度。
- 邊界處理：當數組長度為
1時，直接返回True（無需跳躍即可到達終點）；當某位置不可達時，后續位置必然不可達，提前終止遍歷。
該解法通過線性掃描和常數空間，高效解決了跳躍游戲問題，是此類問題的最優解法。
題目：跳躍游戲 II
給定一個非負整數數組 nums，你最初位于數組的第一個位置，數組中的每個元素代表你在該位置可以跳躍的最大長度。目標是使用最少的跳躍次數到達最后一個位置。
解法：貪心算法
通過維護當前跳躍的最遠可達位置 max_reach 和當前跳躍的終點 end，遍歷數組時更新這些變量。當到達當前跳躍的終點時，跳躍次數加 1，并將終點更新為新的最遠可達位置。若最遠可達位置已覆蓋最后一個位置，提前結束遍歷。
Python 代碼
from typing import List class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) steps = 0 # 跳躍次數 end = 0 # 當前跳躍的終點 max_reach = 0 # 目前能到達的最遠位置 for i in range(n - 1): max_reach = max(max_reach, i + nums[i]) if i == end: steps += 1 end = max_reach if end >= n - 1: break # 已到達或超過最后一個位置，提前結束 return steps
算法分析
- 時間復雜度：( O(n) )，遍歷數組一次，每個元素處理時間為常數。
- 空間復雜度：( O(1) )，僅使用常數級額外空間。
該算法通過貪心策略，每次在可跳躍范圍內找到最遠可達位置，確保跳躍次數最少，高效解決問題。
題目：不同路徑
一個機器人位于一個 m x n 網格的左上角，每次只能向下或者向右移動一步，試圖達到網格的右下角。求總共有多少條不同的路徑？
解法：動態規劃
定義 dp[i][j] 表示到達網格 (i, j) 位置的不同路徑數。
- 初始條件：
- 第一行
dp[0][j] = 1（只能一直向右移動）。 - 第一列
dp[i][0] = 1（只能一直向下移動）。
- 第一行
- 狀態轉移方程：
dp[i][j] = dp[i-1][j] + dp[i][j-1]（從上方或左方到達）。
Python代碼
from typing import List class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m-1][n-1]
優化空間（一維數組）
from typing import List class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [1] * n for i in range(1, m): for j in range(1, n): dp[j] += dp[j-1] return dp[n-1]
算法分析
- 時間復雜度：( O(m \times n) )，兩層循環遍歷網格。
- 空間復雜度：
- 二維數組：( O(m \times n) )。
- 一維數組：( O(n) )，優化后僅用一行數組存儲狀態。
通過動態規劃，利用狀態轉移方程高效計算路徑數，確保每個位置的路徑數由相鄰位置推導而來，最終得到右下角的路徑總數。
