《Leetcode》-面試題-hot100-動態規劃

題目列表

70. 爬樓梯簡單難度 leetcode鏈接
118. 楊輝三角簡單難度 leetcode鏈接
198. 打家劫舍中等難度 leetcode鏈接
279.完全平方數中等難度 leetcode鏈接
322.零錢兌換中等難度 leetcode鏈接
139.單詞拆分中等難度 leetcode鏈接
300.最長遞增子序列中等難度 leetcode鏈接
152.乘積最大子數組中等難度 leetcode鏈接
416.分割等和子集中等難度 leetcode鏈接
32.最長有效括號困難難度 leetcode鏈接

題目

（1）爬樓梯

題目

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2 輸出：2 解釋：有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階

示例 2：

輸入：n = 3 輸出：3 解釋：有三種方法可以爬到樓頂。 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階

提示：

1 <= n <= 45

思路

class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return n        dp = [0] * 3dp[1] = 1dp[2] = 2        for i in range(3, n + 1):total = dp[1] + dp[2]dp[1] = dp[2]dp[2] = total        return dp[2]

（2）楊輝三角

題目

給定一個非負整數 numRows，生成「楊輝三角」的前 numRows 行。

在「楊輝三角」中，每個數是它左上方和右上方的數的和。

示例 1:

輸入: numRows = 5 輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

輸入: numRows = 1 輸出: [[1]]

提示:

1 <= numRows <= 30

思路

# 時間復雜度：O(numRows^2)。
# 空間復雜度：O(1)。返回值不計入。
class Solution:def generate(self, numRows: int) -> List[List[int]]:c = [[1] * (i + 1) for i in range(numRows)]for i in range(2, numRows):for j in range(1, i):# 左上方的數 + 正上方的數c[i][j] = c[i - 1][j - 1] + c[i - 1][j]return c

（3）打家劫舍

題目

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你不觸動警報裝置的情況下 一夜之內能夠偷竊到的最高金額。

示例 1：

輸入：[1,2,3,1] 輸出：4 解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。

示例 2：

輸入：[2,7,9,3,1] 輸出：12 解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。偷竊到的最高金額 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

思路

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 0:  # 如果沒有房屋，返回0return 0if len(nums) == 1:  # 如果只有一個房屋，返回其金額return nums[0]# 創建一個動態規劃數組，用于存儲最大金額dp = [0] * len(nums)dp[0] = nums[0]  # 將dp的第一個元素設置為第一個房屋的金額dp[1] = max(nums[0], nums[1])  # 將dp的第二個元素設置為第一二個房屋中的金額較大者# 遍歷剩余的房屋for i in range(2, len(nums)):# 對于每個房屋，選擇搶劫當前房屋和搶劫前一個房屋的最大金額dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])return dp[-1]  # 返回最后一個房屋中可搶劫的最大金額

（4）完全平方數

題目

給你一個整數 n ，返回和為 n 的完全平方數的最少數量 。

完全平方數 是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。

示例 1：

輸入：n = 12輸出：3 解釋：12 = 4 + 4 + 4

示例 2：

輸入：n = 13輸出：2 解釋：13 = 4 + 9

提示：

1 <= n <= 10(4)

思路

# 完全背包問題
# 時間復雜度：O(N*sqrt(N))。其中 N=10^4。
#空間復雜度：O(N)。
N = 10000
f = [0] + [inf] * N
for i in range(1, isqrt(N) + 1):for j in range(i * i, N + 1):f[j] = min(f[j], f[j - i * i] + 1)  # 不選 vs 選class Solution:def numSquares(self, n: int) -> int:return f[n]

（5）零錢兌換

題目

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。

計算并返回可以湊成總金額所需的 最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數量是無限的。

示例 1：

輸入：coins = [1, 2, 5], amount = 11輸出：3 解釋：11 = 5 + 5 + 1

示例 2：

輸入：coins = [2], amount = 3輸出：-1

示例 3：

輸入：coins = [1], amount = 0 輸出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2(31) - 1
0 <= amount <= 10(4)

思路

類似于（4）的“完全平方數”求解

# 完全背包問題
# 時間復雜度：O(n?amount)，其中 n 為 coins 的長度。
# 空間復雜度：O(amount)。
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:f = [0] + [inf] * amountfor x in coins:for c in range(x, amount + 1):f[c] = min(f[c], f[c - x] + 1)ans = f[amount]return ans if ans < inf else -1
# 鏈接：https://leetcode.cn/problems/coin-change/solutions/2119065/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-21m5/

（6）單詞拆分

題目

給你一個字符串 s 和一個字符串列表 wordDict 作為字典。如果可以利用字典中出現的一個或多個單詞拼接出 s 則返回 true。

注意：不要求字典中出現的單詞全部都使用，并且字典中的單詞可以重復使用。

示例 1：

輸入: s = "leetcode", wordDict = ["leet", "code"] 輸出: true 解釋: 返回 true 因為 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

輸入: s = "applepenapple", wordDict = ["apple", "pen"] 輸出: true 解釋: 返回 true 因為 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重復使用字典中的單詞。

示例 3：

輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 輸出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 僅由小寫英文字母組成
wordDict 中的所有字符串 互不相同

思路

# 時間復雜度：O(n^2)
# 空間復雜度：O(n)
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:       n=len(s)dp=[False]*(n+1)dp[0]=Truefor i in range(n):for j in range(i+1,n+1):if(dp[i] and (s[i:j] in wordDict)):dp[j]=Truereturn dp[-1]

（7）最長遞增子序列

題目

給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。

子序列 是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

示例 1：

輸入：nums = [10,9,2,5,3,7,101,18] 輸出：4 解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

示例 2：

輸入：nums = [0,1,0,3,2,3] 輸出：4

示例 3：

輸入：nums = [7,7,7,7,7,7,7] 輸出：1

提示：

1 <= nums.length <= 2500
-10(4) <= nums[i] <= 10(4)

思路

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums) <= 1:return len(nums)dp = [1] * len(nums)result = 1for i in range(1, len(nums)):for j in range(0, i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)result = max(result, dp[i]) #取長的子序列return result

（8）乘積最大子數組

題目

給你一個整數數組 nums ，請你找出數組中乘積最大的非空連續子數組（該子數組中至少包含一個數字），并返回該子數組所對應的乘積。

測試用例的答案是一個 32-位 整數。

示例 1:

輸入: nums = [2,3,-2,4] 輸出: 6解釋: 子數組 [2,3] 有最大乘積 6。

示例 2:

輸入: nums = [-2,0,-1] 輸出: 0 解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組

提示:

1 <= nums.length <= 2 * 10(4)
-10 <= nums[i] <= 10
nums 的任何子數組的乘積都保證是一個 32-位 整數

思路

# 動態規劃
class Solution:def maxProduct(self, nums: List[int]) -> int:if not nums: return res = nums[0]pre_max = nums[0]pre_min = nums[0]for num in nums[1:]:cur_max = max(pre_max * num, pre_min * num, num)cur_min = min(pre_max * num, pre_min * num, num)res = max(res, cur_max)pre_max = cur_maxpre_min = cur_minreturn res

（9）分割等和子集

題目

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

示例 1：

輸入：nums = [1,5,11,5] 輸出：true 解釋：數組可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

輸入：nums = [1,2,3,5] 輸出：false 解釋：數組不能分割成兩個元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

思路

class Solution:def canPartition(self, nums: List[int]) -> bool:_sum = 0# dp[i]中的i表示背包內總和# 題目中說：每個數組中的元素不會超過 100，數組的大小不會超過 200# 總和不會大于20000，背包最大只需要其中一半，所以10001大小就可以了dp = [0] * 10001for num in nums:_sum += num# 也可以使用內置函數一步求和# _sum = sum(nums)if _sum % 2 == 1:return Falsetarget = _sum // 2# 開始 0-1背包for num in nums:for j in range(target, num - 1, -1):  # 每一個元素一定是不可重復放入，所以從大到小遍歷dp[j] = max(dp[j], dp[j - num] + num)# 集合中的元素正好可以湊成總和targetif dp[target] == target:return Truereturn False

（10）最長有效括號

題目

給你一個只包含 '(' 和 ')' 的字符串，找出最長有效（格式正確且連續）括號子串的長度。

左右括號匹配，即每個左括號都有對應的右括號將其閉合的字符串是格式正確的，比如 "(()())"。

示例 1：

輸入：s = "(()" 輸出：2 解釋：最長有效括號子串是 "()"

示例 2：

輸入：s = ")()())" 輸出：4 解釋：最長有效括號子串是 "()()"

示例 3：

輸入：s = "" 輸出：0

提示：

0 <= s.length <= 3 * 10(4)
s[i] 為 '(' 或 ')'

思路

# 時間復雜度: 每個字符最多入棧，出棧各一次。再加上統計1的個數，最多為 O(3n)
# 空間復雜度: O(n)
class Solution:def longestValidParentheses(self, s: str) -> int:stack=[]maxL=0n=len(s)tmp=[0]*n         #標記數組cur=0for i in range(n):if s[i]=='(':stack.append(i)else:if stack:j=stack.pop()tmp[i],tmp[j]=1,1      #匹配成功時標記    for num in tmp:    #計算連續1出現的最大次數if num:cur+=1else:          #遇到0時中斷，進行對比，并重置maxL=max(cur,maxL)  cur=0maxL=max(cur,maxL) #最后一次統計可能未終斷，多做一次對比return maxL

結尾

親愛的讀者朋友：感謝您在繁忙中駐足閱讀本期內容！您的到來是對我們最大的支持??

正如古語所言："當局者迷，旁觀者清"。您獨到的見解與客觀評價，恰似一盞明燈💡，能幫助我們照亮內容盲區，讓未來的創作更加貼近您的需求。

若此文給您帶來啟發或收獲，不妨通過以下方式為彼此搭建一座橋梁： ? 點擊右上角【點贊】圖標，讓好內容被更多人看見 ? 滑動屏幕【收藏】本篇，便于隨時查閱回味 ? 在評論區留下您的真知灼見，讓我們共同碰撞思維的火花

我始終秉持匠心精神，以鍵盤為犁鏵深耕知識沃土💻，用每一次敲擊傳遞專業價值，不斷優化內容呈現形式，力求為您打造沉浸式的閱讀盛宴📚。

有任何疑問或建議？評論區就是我們的連心橋！您的每一條留言我都將認真研讀，并在24小時內回復解答📝。

愿我們攜手同行，在知識的雨林中茁壯成長🌳，共享思想綻放的甘甜果實。下期相遇時，期待看到您智慧的評論與閃亮的點贊身影?！

萬分感謝🙏🙏您的點贊👍👍、收藏?🌟、評論💬🗯?、關注??💚

自我介紹：一線互聯網大廠資深算法研發（工作6年+），4年以上招聘面試官經驗（一二面面試官，面試候選人400+），深諳崗位專業知識、技能雷達圖，已累計輔導15+求職者順利入職大中型互聯網公司。熟練掌握大模型、NLP、搜索、推薦、數據挖掘算法和優化，提供面試輔導、專業知識入門到進階輔導等定制化需求等服務，助力您順利完成學習和求職之旅（有需要者可私信聯系）?

友友們，自己的知乎賬號為“快樂星球”，定期更新技術文章，敬請關注！