256. Paint House
題目網址：https://leetcode.cn/problems/paint-house/
題意：假如有一排房子, 共 n 間, 每間房子可以被刷成紅、藍 、綠這三種顏色中的一種, 刷所有的房子, 並使其相鄰的兩間房子顏色不能相同。
由於市場上不同顏色的油漆其價格是不同的, 所以房子刷成不同顏色的成本也是不同的。每間房子刷成不同顏色的花費是以一個 n x 3 的正整數 matrix costs 來表示的。
e.g. costs[0][0] 表示第 0 號房子刷成紅色的成本；costs[1][2] 表示第 1 號房子刷成綠色的成本, 依此類推…
計算刷完所有房子所需的最少花費。
Solution 1：
想法：利用 DP
1. 定義狀態：
首先, 會在 costs 前先加上 {0,0,0}, 代表什麼元素都沒有的狀態
dp[i][j] 為前 i 間房子中, 其中第 i 間房子刷成第 j 種顏色所需的最少成本
2. 得到狀態轉移方程：
dp[i][j] = min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) ...
376. Wiggle Subsequence
題目網址：https://leetcode.cn/problems/wiggle-subsequence/
題意：如果連續數字之間的差值在正數和負數之間交替, 則該 subsequence 稱為 Wiggle Subsequence。第一個差值（如果存在的話）可能是正數 or 負數。僅有一個元素 or 兩個不相等元素的 subsequence 也被視作 Wiggle Subsequence。
e.g. [1, 7, 4, 9, 2, 5] 是一個 Wiggle Subsequence, 因為差值 (6, -3, 5, -7, 3) 是正負交替出現的。
subsequence 可以通過從原 array 中刪除一些（也可以不刪除）元素來獲得, 剩下的元素保持其原先順序。
給一整數 array nums, 返回 nums 中 最長 Wiggle Subsequence 的長度。
進階：設計 $O(n)$ time 的演算法。
Solution 1：
想法：利用 DP
1. 定義狀態：
首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
up[i] 代表 nums ...
438. Find All Anagrams in a String
題目網址：https://leetcode.cn/problems/find-all-anagrams-in-a-string/
題意：給兩 string s 和 p, 找到 s 中所有 p 的異位詞, 並返回這些 substring 的起始 index。
異位詞：由相同字母重排列形成的 string（包括相同的 string）
Solution：
想法：利用 Sliding Window, 同 567. Permutation in String
class Solution {public: vector<int> findAnagrams(string s, string p) { int left = 0, right = 0; unordered_map<char, int> window, need; for (const auto& ch : p) { ++need[ch]; } int vali ...
1293. Shortest Path in a Grid with Obstacles Elimination
題目網址：https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/
題意：給一 m x n 的矩陣 grid, 其中每個 cell 不是 0（空）就是 1（障礙物）。每一步都可以在空白 cell 中上、下、左、右移動。
另給一整數 k, 代表最多可以消除 k 個障礙物。
返回從左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路徑長度。若找不到這樣的路徑, 則返回 -1。
Solution：
想法：看到走迷宮求最短路徑, 馬上想到 BFS。我們可以使用 (y, x, e) 代表一個搜索狀態, 其中 (y, x) 代表當前位置, e 代表當前消除障礙物的個數。此外, 我們還需用 visited 來記錄已拜訪的位置, 避免重複拜訪
當 grid[i][j] == 1 時：若當前消除障礙物的個數 e 小於 k, 且 visited[i][j][e + 1] = false ➔ 可以選擇消除此障礙物, 並把 (i, j, e + 1) push 到 q 中
當 grid[ ...
843. Guess the Word
題目網址：https://leetcode.cn/problems/guess-the-word/
題意：給一由不同 string 所組成的單字列表 words, 其中 words[i] 長度均為 6。words 中的一個單字將被選作秘密單字 secret。
另外, 給一輔助對象 Master, 你可以調用 Master.guess(word) 來猜單字, 其中參數 word 長度為 6, 且必須是 words 中的 string。
Master.guess(word) 將會返回以下結果：
若 word 不是 words 中的 string, 則返回 1
返回一個整數, 表示你所猜測的單詞 word 與 secret 的準確匹配（值和位置同時匹配）的數目
此外, 還會給一參數 allowedGuesses, 代表調用 Master.guess(word) 的最大次數。
在不超過允許猜測次數的前提下, 你應該調用 Master.guess 來猜出 secret, 並得到以下結果：
若調用 Master.guess 的次數大於 allowedGuesses or 你沒有用 Mast ...