727. Minimum Window Subsequence
題目網址：https://leetcode.cn/problems/minimum-window-subsequence/
題意：給兩 string s1、s2, 找出 s1 中最短的連續 substring w, 使得 s2 是 w 的 subsequence。
如果 s1 中沒有 window 可以包含 s2 中的所有 char, 則返回 ""。如果有不只一個最短長度的窗口, 則返回開始位置最靠左的那個。
注意：s1、s2 皆只由小寫英文所組成。
Solution：
想法：利用 DP
1. 定義狀態：
首先, 會在 s1、s2 前先加上一個 #, 代表什麼元素都沒有的狀態
dp[i][j]：以 s[i] 為結尾, 用 s1[1:i]、s2[1:j] 的 Minimum Window Subsequence 之長度
2. 得到轉移方程：
令 s1[1:i] = XXXXi, s2[1:j] = YYYj
若 s1[i] == s2[j], 則 [XXXX]、[YYY] 建構的 substring 加上 s1[i] 即可➔ dp[i][j] = dp[i ...
879. Profitable Schemes
題目網址：https://leetcode.cn/problems/profitable-schemes/
題意：集團里有 n 名員工, 他們可以完成各種各樣的工作創造利潤。
第 i 種工作會產生 profit[i] 的利潤, 它要求 group[i] 名成員共同參與。如果成員參與了其中一項工作, 就不能參與另一項工作。
選取一些工作, 這些工作需產生至少 minProfit 的利潤, 且工作的成員總數不得超過 n。
有多少種方案可以選擇？因為答案很大, 所以返回結果 mod $10^9 + 7$ 的值即可。
Solution 1：
想法：利用 DP, 本題有兩種容量, 因此使用三維 DP
1. 定義狀態：
首先, 會在 group、profit 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][j][k]：前 i 個工作中「恰好」選擇了 j 個員工, 並滿足利潤為「至少」為 k 的方案數
2. 得到轉移方程：
第 i 個工作有「選 or 不選」兩種選擇：
若不選, 則要用前 i - 1 個工作完成選擇 j 個員工, 並滿足最小利潤為 k ➔ dp[i][j][k ...
956. Tallest Billboard
題目網址：https://leetcode.cn/problems/tallest-billboard/
題意：你正在安裝一個廣告牌, 並希望它高度最大。這塊廣告牌將有兩個鋼制支架, 兩邊各一個, 且每個鋼支架的高度必須相等。
你有一堆可以焊接在一起的鋼筋 rods, e.g. 如果鋼筋的長度為 1、2 和 3, 則可以將它們焊接在一起形成長度為 6 的支架。
返回廣告牌可能的最大安裝高度, 如果無法安裝廣告牌, 則返回 0。
Solution 1：(TLE 無法通過)
想法：利用 DP
1. 定義狀態：
首先, 會在 rods 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][j][k]：rods[1:i] 中湊出左邊為 j、右邊為 k 是否可行
2. 得到轉移方程：
rods[i] 有「選 or 不選」兩種可能：
rods[i] 不選, 則 dp[i][j][k] = dp[i - 1][j][k]
rods[i] 要選（rods[i] = h）：
將 rods[i] 加入左邊, 則 dp[i][j][k] = dp[i - 1][j - h][k]
將 rod ...
903. Valid Permutations for DI Sequence
題目網址：https://leetcode.cn/problems/valid-permutations-for-di-sequence/
題意：給一長度為 n 的 string s , 其中 s[i] 可能是：
D 代表減少
I 代表增加
有效排列是對在 [0, n] 範圍內的所有整數的一個排列 perm, 使得對所有的 i 滿足以下規則：
若 s[i] == 'D', 則 perm[i] > perm[i + 1]
若 s[i] == 'I', 則 perm[i] < perm[i + 1]
返回有效排列 perm 的數量, 因為答案可能很大, 所以請返回你的答案對 $10^9 + 7$ 取餘數。
Solution 1：
想法：利用 DP, 由於 s[i] 決定的只是 perm 中的「相對」大小, 故 perm[i] 的值僅由 s[i - 1] 和 perm[i - 1] 決定。
1. 定義狀態：
首先, 會在 s 前先加上一個 #, 代表什麼元素都沒有的狀態
dp[i][j]：s[1:i] 中, 結尾為 perm[i] ...
546. Remove Boxes
題目網址：https://leetcode.cn/problems/remove-boxes/
題意：給一些不同顏色的盒子 boxes, 盒子的顏色由不同的正數表示。
你將經過若干輪操作去移除盒子, 直到所有的盒子都被移除為止。每一輪你可以移除具有相同顏色的連續 k 個盒子（k ≥ 1）, 這樣一輪之後你將得到 k * k 個積分。
返回你能獲得的最大積分和。
Solution：
想法：我們很容易陷入這樣一個錯誤的思路：用 dfs(l, r) 來表示移除區間 [l, r] 內所有的盒子能得到的最大積分, 然後去探索某一種移除盒子的策略來進行狀態轉移。但實際上, 我們並不能直接使用起點和終點來決定最大分數, 因為這個分數並不只依賴於 subarray, 也依賴於之前的移動對 array 的影響（概念類似 312. Burst Balloons）, 最終的 subarray 在原先的 array 中可能不是連續的。
e.g. boxes = [3,4,2,4,4]
若先移除 2, 使 [3,4,2,4,4] ➔ [3,4,4,4], 再移除 3 個 4➔ 對積分的貢獻為 $1^2 ...