Dynamic Programming

518. Coin Change 2 class Solution: def change(self, amount: int, coins: List[int]) -> int: ans = [] memo = {} def helper(target, index): if (target, index) in memo: return memo[(target, index)] if target < 0: memo[(target, index)] = 0 elif target == 0: memo[(target, index)] = 1 else: count = 0 for i

448. Find All Numbers Disappeared in an Array 這個題目的簡單做法是排序後再找，但是這樣的做法通常都是會被問到提供更好的解法。 關於解法其實也不難，那就是使用 Set 記錄起來有出現過的元素，之後從小走到大，再把沒有出現在 Set 裡面的數字記錄起來，那就可以找到解答了。 class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: m = len(nums) S = set(nums) ans = [] for i in range(1, m + 1): if i not in S: ans.

651. 4 Keys Keyboard 這個題目滿有趣的，為了幫助大家對這個題目有更深的印象，我分享一個小故事，我在剛開始學寫程式的時候，是從 HTML 和 CSS 開始學起，當時看到迴圈就頭痛，以為只要學好 HTML 加上 CSS 就能當前端工程師，那時候響應式設計剛興起，Twitter Bootstrap 才剛出了第一版，我為了要測試當網站的內容很多的時候，看看網站變得很長會怎麼樣，也就很土法煉鋼的複製一段文字，接著一直貼上，貼了幾段後發現，我應該要全選所有的文字，再重新複製一次，在繼續一直貼上，這樣子一次會產生更多的內容會更快，一直貼上到一定的程度後，就要重新再全選一次、複製、再繼續動作...不斷重複。 這一個題目設計的情況就是這樣，有一個鍵盤，只有四個按鈕：A，全選，複製，貼上。我們可以隨便按任何鍵，可是總共按的次數只有 n 次。試問我們要怎麼樣建立出最長的一個字串？ 以前我在複製的時候很隨性，

10. Regular Expression Matching 這一題是正規表達式的題目，主要有兩個符號要考慮：「.」和「*」，點號和星號，點號比較好處理，因為只要是點好，就代表可以跳過該字元，最難處理的是星號；因為星號可以代表的是該字元可以出現零到無限次。其中又以.* 代表的是可以符合任何字元無限次。 下面是如果只以 . 當作匹配的字串時所做的考量。 class Solution: def isMatch(self, s: str, p: str) -> bool: i = 0 j = 0 while i < len(s) and j < len(p): if s[i] == p[j] or p[j] == '.':

416. Partition Equal Subset Sum 首先我們要確立目標，目標是給定一個陣列能不能分成兩個子集合，讓這兩個子集合的總和相等。 第一個要去想的地方比較簡單，既然兩個子集合要相等，那一個子集合一定是原陣列總和的一半，我們的目標就是要找到一個一個子集合，其總和是原陣列總和的一半。 另外，有可能原陣列的元素總和是奇數：例如：[1, 2, 1, 1] 這樣的陣列總和是 5 ，一定不會有辦法分成兩個集合，所以可以先用這樣的方式去剪枝（把所有總和為奇數的直接排除掉）。 接著是要怎麼選擇，每一個元素我們都可以有「選」或是「不選」這兩種方式，如果選的話，我們的目標就會減少當下的數值，如果不選的話，目標並不會改變，一直到如果我們選了最後一個數字，如果最後目標剛好等於 0 ，那就是我們透過選擇，找到了目標。 這樣的關係可以用一個遞迴的方式來呈現。 遞迴 class Solution: def canPartition(self, nums: List[int]

115. Distinct Subsequences class Solution: def numDistinct(self, s: str, t: str) -> int: memo = defaultdict(int) def helper(i, j): if i == len(s) and j == len(t): return 1 elif i == len(s): return 0 elif j == len(t): return 1 if (i, j) in memo: return memo[