Backtrack 是 DFS 的一種形式，基本寫法類似於 TOP DOWN DFS，處理方式就是所謂的窮舉法，將所有可能的結果都找出來；每一個結果都實際看看這樣。換個角度來說，其實這個過程就如同在樹上遍歷 (Tree Traversal) ，而普通的 DFS 是不需要回溯狀態的。 Backtrack 強調了狀態回溯。
這題是非常有名的 Fibonacci 數列，其特徵是除了前兩個數字之外，每個數字等於前兩個數字之和。解法可以帶出一些經典觀念和想法，例如 :
- Dynamic Programming
- 迭帶 for-loop
- recursion 遞迴
由於 Fibonacci 數列的時間空間複雜度計算比較特別，加上可以很初步引入很多的思考方式，故雖然這題是 easy ，我還是做個紀錄。
這題真的蠻難的，一開始看題目我也覺得很繞口，給了一個非負數的 nums 和一個 m 代表把 nums 分成 m 個 group 且 每個 group non-empty 並取 m 個 group 中的最大值。但注意，前面只是代表一種切法而已，我們是要找所有可能切法之中的最小值。看一下 Related Topics 發現可以用 Binary Search 和 DP 求解，也是一道高頻題目。
石頭遊戲，兩個人輪流選石頭，Alex 先選，每次只能選開頭或結尾，最終獲得石頭總數多的人獲勝。 乍看之下不好想到可以用 DP 解，但其實可用一個 2D-state 去描述遞迴的狀態。 這題一開始會好奇是因為負評倒讚很多，個人是感覺能從 Game Theory 單純想出這結論也是蠻厲害的…
這題是求最長相同的子序列，可用 Dynamic Programing 來做，最難的還是想出狀態函數。這裡使用 2D-dp ，其中 dp[i][j] 表示 :
- text1 的前 i 個字符
- text2 的前 j 個字符
的最長相同的子序列的字符個數
這題是 62. Unique Paths 的延伸，能選擇往下或往右走直至終點為止，要求出有多少種可能走法，但多了一個限制，會在路徑中加了一些 obstacle 擋住了某些路徑。是一道典型的 Dynamic Programming - 2D matrix 類型的題目。和爬樓梯等都屬於動態規劃中常見題目，因此也經常會被用於面試之中。
一道很經典的題目，是給定一 string ，能不能分被拆分成 wordDict 裡面的單詞。注意這題，wordDict 裡面的單詞可以重複使用，即單詞使用沒有次數限制，所以 string 可以分成任意段，這就增加了題目的難度。解法蠻多種的，可先從 brute force 下手，再加上暫存優化後，就是蠻標準的 dp 解了，來解一下吧。
Dynamic Programming 大概算是 leetcode 裡面平均難度最高的章節了，還蠻需要練習的。但在講 DP 之前，我們可以先講 Search，因為 Dynamic Programming 其實就是 Search + Memoization。
最長回文子串 (Longest Palindromic Substring) 是常考題。Palindrome 就是正讀反讀都一樣的詞語，比如範例給的 “bab”、 “bb” ，實際單字如 “level” 等等都屬於它。因為較好的解法是 DP 類型，初見就能想到，難度也比較高。一般人能熟悉 Dynamic Programming - 2D matrix 解就好了。(看過令人膜拜的神解 Manacher’s Algorithm，時間複雜度提升到了 O(n) …)