416. Partition Equal Subset Sum
題目網址：https://leetcode.cn/problems/partition-equal-subset-sum/
題意：給一只含正整數的非空 array nums, 返回是否能將 nums 切割成兩個 subset, 使得兩個 subset 的元素和相等。
Solution 1：
想法：利用 DP, 因為此題可看作是 0-1 背包問題, 從前 i 個數中取出一些數, 使這些數之和為 target, 其中 dp[i][j] 代表前 i 個數是否能取出一些數, 使得這些數和為 j, 可得以下公式：
不選擇 nums[i]：dp[i][j] = dp[i - 1][j]
選擇 nums[i]：dp[i][j] = dp[i - 1][j - nums[i]], 其中 j >= nums[i]
class Solution {public: bool canPartition(vector<int>& nums) { const int sum = accumulate(nums.begin(), nums ...
62. Unique Paths
題目網址：https://leetcode.cn/problems/unique-paths/
題意：有一機器人位於 m x n 網格的左上角, 機器人每次只能往下 or 往右一步, 機器人試圖抵達網格的右下角, 求總共幾條不同的路徑。
Solution 1：
想法：利用 DP, 定義 dp[i][j] 為從起點到 (i, j) 的方法數, 其中第一列和第一行方法數皆初始化為 1（因為只能往下、右移動）。要避免重複計算（圖中橘色圈起來的部分）, dp[i][j] = 其左邊格子的方法數 + 上方格子的方法數➔ 得到 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
class Solution {public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 1)); for (int i = 1; i < m; ++i) { ...
1143. Longest Common Subsequence
題目網址：https://leetcode.cn/problems/longest-common-subsequence/
題意：給兩 string text1、text2, 返回最長共同 subsequence 的長度。若不存在最長共同 subsequence, 則返回 0。
注意：
substring 指的是 string 中連續的 subset
subsequence 則是 string 的 subset
text1、text2 只由小寫字母所組成
Solution 1：
想法：利用 DP
1. 定義狀態：
首先, 會在 text1、text2 前先加上一個 #, 代表什麼元素都沒有的狀態
dp[i][j]：text1[1:i]、text2[1:j] 的 LCS 之長度
2. 得到轉移方程：
令 text1[1:i] = XXXXi, text2[1:j] = YYYj
若 text1[i] == text2[j], 則 [XXXX]、[YYY] 之 LCS 再加上 text1[i] 即可➔ dp[i][j] = dp[i - 1][j - 1] + 1
否則, ...
309. Best Time to Buy and Sell Stock with Cooldown
題目網址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
題意：給一 array prices, 其中 prices[i] 代表第 i 天的股票價格, 在滿足下列條件的前提下, 盡可能地完成更多的交易, 計算出最大利潤。
賣出股票後, 你沒辦法在下一天買入股票(冷凍期為一天)
不能同時參與多筆交易, 必須在再次購買前出售掉之前的股票
Solution 1：
想法：利用 DP
1. 定義狀態：
首先, 會在 prices 前先加上一個 0, 代表什麼元素都沒有的狀態
rest[i] 代表第 i 天手上未持有股票, 且狀態為 rest 的最大收益
hold[i] 代表第 i 天手上持有股票, 且狀態為 hold 的最大收益（手上持有股票然後休息, 其狀態仍是 hold。rest 狀態必須在未持有股票時）
sold[i] 代表第 i 天手上未持有股票, 且狀態為 sold 的最大收益
2. 根據下圖, 可得狀態轉移方程：
rest[i] = max(rest[i - 1], ...
518. Coin Change II
題目網址：https://leetcode.cn/problems/coin-change-ii/
題意：給一整數 array coins 表示不同面額的硬幣, 和一整數 amount 表示總金額。
返回可以湊成 amount 的硬幣組合數。如果任何硬幣組合都無法湊出總金額, 則返回 0。
假設每一種面額的硬幣有無限個。
題目保證結果符合 32-bit 有號整數。
Solution 1：
想法：利用 DP
1. 定義狀態：
首先, 會在 coins 前先加上一個 0, 代表什麼元素都沒有的狀態
dp[i][j]：前 i 種硬幣湊齊金額 j 的組合數
2. 得到轉移方程：
coins[i] 有「選 or 不選」兩種可能：
rods[i] 不選, 則 dp[i][j] = dp[i - 1][j]
rods[i] 要選, 則 dp[i][j] = dp[i][j - coins[i]]（每一種面額可無限取, 故為 i 而非 i - 1）
3. 初始化：
dp[0][0]：當沒有任何硬幣時, 湊齊金額 0 的組合數為 1（什麼都不選也是一種方案）➔ dp[0][0] = ...