494. Target Sum
題目網址：https://leetcode.cn/problems/target-sum/
題意：給一 array nums 和整數 target, 在 nums 中每個整前添加 + 或 -, 然後串聯整個 nums 形成一個表達式：
e.g. nums = [2, 1] 可以在 2 前添加 +, 在 1 前添加 -, 形成表達式 +2-1
求運算結果等於 target 的不同表達式數目。
Solution 1：
想法：利用暴力法, 遞迴下去做（速度極慢）
class Solution {public: int findTargetSumWays(vector<int>& nums, int target) { const int sum = accumulate(nums.begin(), nums.end(), 0); if (target > abs(sum) || target < -abs(sum)) { return 0; ...
97. Interleaving String
題目網址：https://leetcode.cn/problems/interleaving-string/
題意：給三個 string s1、s2、s3, 返回 s3 是否是由 s1 和 s2 交錯組成的。
兩個 sting s、t 交錯的定義與過程如下, 其中每個 string 都會被分割成若干個 non-empty substring：
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交錯是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或 t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 代表 string a 和 b 串接。
Solution：
想法：利用 DP, 其中 dp[i][j] 表示 s1 前 i 個 char 和 s2 前 j 個 char 能否構成 s3 前 i + j 個 char
dp[i][j] 為 true 有兩種情況：
s1[i - 1] == s3[i + j - 1] && dp[i - ...
312. Burst Balloons
題目網址：https://leetcode.cn/problems/burst-balloons/
題意：給一整數 array nums 表示所有氣球上的編號。
戳破第 i 個氣球, 可以獲得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬幣。其中 i - 1 和 i + 1 代表與 i 相鄰的兩個氣球之編號。若 i - 1 或 i + 1 超出了 nums 的邊界, 則將其看作是編號為 1 的氣球。
返回戳破所有氣球所能獲得的最大硬幣數。
注意：1 ≤ nums[i] ≤ 300
Solution：
想法：利用 DP
本題重點：
與其考慮先射爆哪個氣球, 不如考慮最後射爆哪個氣球。因為如果是考慮先射爆哪個氣球, 這種方式無法確定當前左、右邊的氣球編號。
若是考慮最後射爆哪個氣球, 則可以確定該氣球的左、右邊編號
1. 定義狀態：
dp[i][j]：在 nums[i:j] 中最後射爆 index = k 的氣球
在射爆 idx = k 的氣球前, 必須先射爆 nums[i:(k-1)]、nums[(k+1):j] 區間中的氣球
2. 得到狀態 ...
53. Maximum Subarray
題目網址：https://leetcode.cn/problems/maximum-subarray/
題意：給一 array nums, 找到一 subarray, 其元素和為所有 subarray 中最大的。
注意：subarray 必須是連續的（index 不可中斷）
Solution 1：
想法：利用 DP, 每個元素都有加入 or 不加入 subarray 兩種選擇。若不加入, 則該元素成為新的 subarray 的開頭繼續往後尋找, 其中 dp[i] 代表 [0, i] 這個區間中擁有最大和的 subarray 之和
class Solution {public: int maxSubArray(vector<int>& nums) { const int n = nums.size(); int res = nums[0]; vector<int> dp(n, nums[0]); for (int i = 1; i < n; ++i) { ...
55. Jump Game
題目網址：https://leetcode.cn/problems/jump-game/
題意：給一非負整數 array nums, 最初位置在 nums[0], 其中 nums 中的每個元素代表該位置可以跳躍的最大長度, 返回是否能從起點抵達最後一個 index。
Solution 1：
想法：利用 DP, 其中 dp[i] 代表第 i 個點能否被抵達, 條件是 i 前面的任意點 j 能被抵達 （dp[j] = true）, 且能從 j 跳到 i （j + nums[j] >= i ）, 故得到狀態轉移方程：
dp[i] = (dp[j] == true) && (j + nums[j] >= i), 其中 0 ≤ j < i
從下圖中可看到, 從 idx = 2 開始往後走的有重複, 故用 cache 把結果存起來, 避免重複計算
class Solution {public: bool canJump(vector<int>& nums) { const int n = n ...