這題是 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 」 也是一個的 Palindromic 單字。
先熟悉「 Dynamic Programming - 2D matrix 」解和「 中心擴散法 (Expand Around Center) 」就好了，還有聽過最佳解 Manacher’s Algorithm，時間複雜度可優化到了 O(n)，之後再花其他篇幅去補充。