123. Best Time to Buy and Sell Stock III
題目網址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
題意：給一整數 array prices, 其中第 i 個元素代表第 i 天的股價。
最多完成兩筆交易, 返回最大利潤。
注意：不能同時參與多筆交易（必須在再次購買前出售掉之前的股票）。
Solution 1：
想法：利用 DP
1. 定義狀態：
首先, 會在 prices 前先加上一個 0, 代表什麼元素都沒有的狀態
hold1[i]：第 i 天買入第一支股票的最大收益
sold1[i]：第 i 天賣出第一支股票的最大收益
hold2[i]：第 i 天買入第二支股票的最大收益
hold2[i]：第 i 天賣出第二支股票的最大收益
2. 得到狀態轉移方程：
hold1[i]：可由以下兩種狀態轉移
第 i - 1 天買入第一支, 第 i 天不操作 ➔ hold1[i - 1]
第 i - 1 天不操作（沒任何股票）, 第 i 天買入第一支 ➔ 0 - prices[i]
➔ hold1[i] = max(hold1[i - 1] ...
1335. Minimum Difficulty of a Job Schedule
題目網址：https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/
題意：你需要制定一份 d 天的工作計劃表, 每個工作之間是互相依賴的, 要想執行第 i 項工作, 則必須完成前 j 項工作（0 ≤ j < i）。
每天至少需要完成一項任務, 工作計劃的總難度是這 d 天每一天的難度之和, 而一天的工作難度是當天應該完成工作的最大難度。
給一整數 array jobDifficulty 和一整數 d, 分別代表工作難度和需要計劃的天數, 其中第 i 項工作的難度是 jobDifficulty[i]。
返回整個工作計劃的最小難度。若無法制定工作計劃, 則返回 -1。
Solution：
想法：利用 DP
1. 定義狀態：
首先, 會在 jobDifficulty 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][k]：jobDifficulty[1:i] 分割成 k 個 subarray 的最小難度和
2. 得到轉移方程：
dp[i][k] = min(dp[i][k], dp[j - ...
1092. Shortest Common Supersequence
題目網址：https://leetcode.cn/problems/shortest-common-supersequence/
題意：給兩 string str1 和 str2, 返回同時以 str1 和 str2 作為 subsequence 的最短 string。如果答案不止一個, 則返回滿足條件的任意一個答案。
如果從 string T 中刪除一些char（也可能不刪除, 並且選出的這些 char 可以位於 T 中的任意位置）, 可以得到 string S, 那麼 S 就是 T 的subsequence）
注意：str1、str2 皆由小寫字母所組成。
Solution：
想法：利用 DP
1. 定義狀態：
首先, 會在 str1、str2 前先加上一個 #, 代表什麼元素都沒有的狀態
dp[i][j]：str1[1:i]、str2[1:j] 的 SCS 之長度
2. 得到轉移方程：
若 str1[i] == str2[j]：此時的 SCS 為原先的 SCS 加上 str1[i] 即可➔ dp[i][j] = dp[i - 1][j - 1] + 1
否則, 此時的 ...
410. Split Array Largest Sum
題目網址：https://leetcode.cn/problems/split-array-largest-sum/
題意：給一非負整數 array nums 和一整數 k, 將 nums 分成 k 個非空的連續 subarray。
設計一個演算法最小化這 k 個 subarray 和的最大值（盡可能讓每個 subarray 之和都差不多）。
Solution：
想法：利用 DP
1. 定義狀態：
首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][k]：nums[1:i] 中 k 個 subarray 和的最大值之最小化
2. 得到轉移方程：
dp[i][k] = min(dp[i][k], max(dp[j - 1][k - 1], sum)), 其中 1 ≤ j ≤ i
最後一個元素 nums[i], 必定是在當前最後一個連續 subarray 中, 因此要考慮這個區間的起始元素 j 會在哪裡 ➔ 故從 i 往前倒推
3. 初始化：
dp[0][0]：空 array 可分割成 0 個 subarray, 且 subarray 最大和最 ...
1246. Palindrome Removal
題目網址：https://leetcode.cn/problems/palindrome-removal/
題意：給一整數 array arr, 每次操作你都可以刪除一個回文 subarray arr[i], arr[i+1], ..., arr[j]（i ≤ j）。
每當你刪掉一個 subarray, 其右側元素會向前填補空位。
計算從 arr 中刪除所有數字所需的最少操作數。
Solution：
想法：利用 DP, 當找不出突破口時, 試著從最後一個元素下手
1. 定義狀態：
首先, 會在 arr 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][j]：arr[i:j] 刪除所有數字的最小操作數
2. 得到轉移方程：
要在 arr[i:j] 中找回文, 就先判斷 arr[j] 要和哪個數消除
若 arr[j] 和 arr[k] 相等時, 則一同消除, 其中 i ≤ k ≤ j ➔ dp[i][j] = dp[i + 1][k] + dp[k + 1][j - 1]
當 dp[k + 1][j - 1] 不為空區間時, 則 arr[k]、arr[j] 可以被算 ...