91. Decode Ways
題目網址：https://leetcode.cn/problems/decode-ways/
題意：給一只含數字的非空 string s，計算並返回解碼的方法數
一則包含字母 A-Z 的訊息透過以下 mapping 進行編碼:
要解碼已編碼的訊息, 其所有數字必須基於上述 mapping 的方法，反向 mapping 回字母（可能有多種方法）。例如 : “11106” 可以 mapping 為：
AAJF 將訊息分組為 (1 1 10 6)
KJF 將訊息分組為 (11 10 6)
注意：訊息並不能分組為 (1 11 06), 因為 06 並不能 mapping 為 F, 這是因為 6 和 06 在 mapping 中並不等價
答案保證符合 32-bit 整數的範圍
Solution 1：（TLE 無法通過）
想法：利用 DFS, 其中每個 char 都有兩種選擇：
自己一組, 前提是自己不能為 '0'。若為 '0', 則一定要跟其他 char 一組
自己 + 後面一個 char 一組, 前提是 "10" <= s ...
322. Coin Change
題目網址：https://leetcode.cn/problems/coin-change/
題意：給一整數 array coins, 表示不同面額的零錢, 和一整數 amount 代表總金額。
計算可以湊成 amount 的最少硬幣數。如果無法湊成, 則返回 -1。
每種硬幣的數量都是無限的。
Solution 1：（TLE 無法通過）
想法：利用 DFS
普通版：DFS
class Solution {public: int coinChange(vector<int>& coins, int amount) { int res = amount + 1, count = 0; dfs(coins, amount, count, res); return (res == amount + 1) ? -1 : res; }private: void dfs(const vector<int>& coins, const int amount ...
152. Maximum Product Subarray
題目網址：https://leetcode.cn/problems/maximum-product-subarray/
題意：給一整數 array nums, 找出乘積最大的非空連續 subarray, 並返回該乘積。
Solution：
想法：定義乘積為區間 [0, i] 中的最大 or 最小乘積。為何乘積必須同時記錄 curMax 和 curMin？因為 array 中可能會有負數, 且負負得正。當 nums[i] 為負數時, 之前紀錄的 curMax 乘它之後變最小值, 也有可能之前紀錄的 curMin 乘它之後變比之前的 curMax 還大。所以當 nums[i] 為負數時, 要將 curMax 和 curMin 做 swap, 這樣才不會出錯
class Solution {public: int maxProduct(vector<int>& nums) { int curMax = 1, curMin = 1, res = nums[0]; for (const auto& num ...
139. Word Break
題目網址：https://leetcode.cn/problems/word-break/
題意：給一 string s 和一 string list wordDict, 若 wordDict 中的單字能組出 s 則返回 true。
注意：wordDict 中的 string 互不相同, 且 s.length ≤ 300
Solution 1：
想法：利用 DP, 其中 dp[i] 代表 s[0~(i-1)] 是否能被拆分成若干個出現在 wordDict 中的單字, 我們要枚舉 s[0~(i-1)] 中的切割點 j, 使得 s[0~(j-1)] 和 s[j~(i-1)] 皆在 wordDict 中, 由於 j < i, 所以要計算 dp[i] 時可透過先前計算過的 d[j] 知道 s[0~j] 是否能被拆分, 然後再判斷 s[j~(i-1)] 是否在 wordDict 中即可, 故得到以下公式：
dp[i] = dp[j] && check(s[j~(i-1)])
check(s[j~(i-1)]) 代表檢查 s[j~(i-1)] 是否在 wordDict ...
300. Longest Increasing Subsequence
題目網址：https://leetcode.cn/problems/longest-increasing-subsequence/
題意：給一整數 array nums, 找出其中最長的嚴格遞增 subarray 之長度。
進階：設計 $O(n \cdot log(n))$ time 的演算法
Solution 1：
想法：利用 DP
1. 定義狀態：
首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i]：nums[1:i] 中 LIS 的長度
2. 得到轉移方程：
dp[i] = max(dp[i], dp[j] + 1), for 1 ≤ j < i
3. 初始化：
dp[0]：當沒有元素時, LIS 的長度為 0
dp[i]：至少一個元素時, LIS 的長度最小為 1, 其中 1 ≤ i ≤ n
res：至少一個元素時, LIS 的長度最小為 1
class Solution {public: int lengthOfLIS(vector<int>& nums) { ...