474. Ones and Zeroes
題目網址：https://leetcode.cn/problems/ones-and-zeroes/
題意：給一二進制 string array strs 和兩整數 m 和 n。
給你 m 個 0 和 n 個 1, 求最多可以組成幾個 strs 中的 string。
Solution 1：
想法：利用 DP, 本題有兩種容量（0、1 數量）, 因此使用三維 DP
1. 定義狀態：
首先, 會在 strs 前先加上一個 "", 代表什麼元素都沒有的狀態
dp[i][j][k]：strs[1:i] 中, 使用 j 個 0 和 k 個 1 最多所能組成的 string 個數
2. 得到轉移方程：
假設 strs[i] 有 zeros 個 0 和 ones 個 1, 則每個 strs[i] 有兩種選擇（選 or 不選）
若 zeros > j 或 ones > k, 則 strs[i] 必不能選（超過個數上限）➔ dp[i][j][k] = dp[i - 1][j][k]
若 zeros ≤ m 或 ones ≤ n：
若 strs[i] 要選 ...
1278. Palindrome Partitioning III
題目網址：https://leetcode.cn/problems/palindrome-partitioning-iii/
題意：給一由小寫字母組成的 string s, 和一整數 k。
請按下面的要求分割 s：
首先, 你可以將 s 中的部分 char 修改為其他的小寫英文字母
接著, 你需要把 s 分割成 k 個非空且不相交的 substring, 並且每個 substring 都是回文
返回以這種方式分割 s 所需修改的最少 char 數目。
Solution 1：
想法：利用 DP
1. 定義狀態：
首先, 會在 s 前先加上一個 #, 代表什麼元素都沒有的狀態
dp[i][k]：s[1:i] 切割成 k 個回文 substring 的最少修改數
2. 得到轉移方程：
dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + helper(s, j, i)), for 1 ≤ j ≤ i
j 初始化成 k 而非 1, 是因為 dp[j - 1][k - 1] 指 nums[1:(j-1)] 拆成 k - 1 個 subarray, ...
983. Minimum Cost For Tickets
題目網址：https://leetcode.cn/problems/minimum-cost-for-tickets/
題意：給一整數 array days 代表旅行的日子, 其中 1 ≤ days[i] ≤ 365。
車票有三種不同的銷售方式 ：
一張 1-day 通行證的售價為 costs[0]
一張 7-day 通行證的售價為 costs[1]
一張 30-day 通行證的售價為 costs[2]
通行證允許數天無限制的旅行。例如, 如果我們在第 2 天獲得一張 7-day 的通行證, 則可以連著旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回滿足 days 中每一天都旅行所需的最低花費。
注意：days 是嚴格遞增的。
Solution：
想法：利用 DP
1. 定義狀態：
dp[i]：代表旅行到第 i 天所需的最小花費
2. 得到轉移方程：
若 i not in days：也就是第 i 天實際上不用旅行, 因此直接使用上一次的狀態即可➔ dp[i] = dp[i - 1]
i in days：有三種選擇, ...
813. Largest Sum of Averages
題目網址：https://leetcode.cn/problems/largest-sum-of-averages/
題意：給一 array nums 和一整數 k, 將 nums 分成最多 k 個相鄰的非空 subarray。分數為每個 subarray 內的平均值之總和。
注意：必須使用 nums 中的每一個數進行分組, 且分數不一定是整數。
返回所能得到的最大分數, 答案誤差在 $10^{-6}$ 內都會被視為是正確的。
Solution：
想法：利用 DP
1. 定義狀態：
首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][k]：nums[1:i] 分成 k 個 group 的平均值之最大總和
2. 得到轉移方程：
dp[i][k] = max(dp[i][k], dp[j - 1][k - 1] + sum / (i - j + 1));, 其中 1 ≤ j ≤ i
最後一個元素 nums[i], 必定是在當前最後一個連續 subarray 中, 因此要考慮這個區間的起始元素 j 會在哪裡 ➔ 故從 i 往前倒推
3. 初始化：
...
375. Guess Number Higher or Lower II
題目網址：https://leetcode.cn/problems/guess-number-higher-or-lower-ii/
題意：我們正在玩一個猜數遊戲, 遊戲規則如下：
我從 1 到 n 之間選擇一個數字
你來猜我選了哪個數字
如果你猜到正確的數字, 就會贏得遊戲
如果你猜錯了, 那麽我會告訴你, 我選的數字比你的更大 or 更小, 並且你需要繼續猜數
每當你猜了數字 x 並且猜錯了的時候, 你需要支付金額為 x 的現金。如果你花光了錢, 就會輸掉遊戲。
給你一個特定的數字 n, 返回能夠確保你獲勝的最小現金, 不管我選擇哪個數字。
Solution：
想法：利用 DP
1. 定義狀態：
dp[i][j]：區間 [i, j] 中確保獲勝的最小現金
2. 得到轉移方程：
選 k 且猜錯, 則確保獲勝的最小金額為 k + max(dp[i][k - 1, dp[k + 1][j])。➔ 取兩個區間中的最大值是因為要確保必須考慮最差情況
dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1], dp[k + 1][j])), ...