91. Decode Ways
這題的題目是如果說給出一串字串，由數字組成，如果要轉換成英文，可以轉換成幾種方式？其中比較特別的就是如果兩個數字剛好不是零為開頭，那像是 "11" 就可以變成 aa 或是 k 像這樣的題目滿像是走樓梯問題的，一次可以走一步或兩步，不過呢，需要注意的是什麼樣的情況下可以走，以及邊界的情況。
既然是走樓梯問題，那就可以先用走樓梯問題的方式來建構題目。
class Solution:
def numDecodings(self, s: str) -> int:
def recursive(index: int) -> int:
# TODO
ans = recursive(index + 1)
ans += recursive(index + 2)
return ans
return recursive(0)我先一算出走一步的有幾種組合，再加上走兩步的有幾種組合，那應該就是答案了吧？很接近，但是我們要注意的是只有 10 ~ 26 是有機會可以當作兩步走的。
class Solution:
def numDecodings(self, s: str) -> int:
def recursive(index: int) -> int:
# TODO
ans = recursive(index + 1)
if 10 <= int(s[index : index + 2]) <= 26:
ans += recursive(index + 2)
return ans
return recursive(0)到了這裡，我們會發現這個遞迴會無限的走下去，因為沒有終止條件。
有哪些終止條件呢？
第一種情況 s[index] == '0' ，以 '10' 來看，先遞迴 '1' 接著是 '0' ，走到 '0' 的瞬間，沒有英文的組合，所以要退回，返回零種組合，這時候走一步的情況無法，接著因為 10 符合條件，所以再走往前走二步，這時候會發生 index == 2 越界的情況。而能夠發生這種情況的，都因為一定會符合這個條件：10 <= int(s[index : index + 2]) <= 26 ，所以會促成下一個終止條件。
第二種情況 index == len(s) 這個會比較難想一點，需要靠上面的例子來想出來，返回一種組合。
第三種情況 index == len(s) - 1 這個很簡單，因為當條件成立，我們走到了最後一位，且也不是 '0' ，所以說可以直接返回一種組合。
而且這題最困難的一個地方，是這三個條件，是有順序性的，一定要是按照以下的方式：
class Solution:
def __init__(self):
self.memo = {}
def numDecodings(self, s: str) -> int:
def recursive(index: int) -> int:
# 要先處理越界，不然下一個條件會報錯
if index == len(s):
return 1
# 再來要看是不是零，因為有可能最後一個數字是零
if s[index] == '0':
return 0
# 沒有越界，也不是零，才是真的到達了終點
if index == len(s) - 1:
return 1
ans = recursive(index + 1)
if 10 <= int(s[index:index + 2]) <= 26:
ans += recursive(index + 2)
return ans
return recursive(0)到了這裡，就會發現其實會有很多重疊的子問題，例如：1111111 這樣的組合，就會有很多的重疊子問題，但因為我們有了遞迴的關係，我們可以直接用自頂向下的方式來記憶。
自頂向下
class Solution:
def numDecodings(self, s: str) -> int:
memo = {}
def recursiveWithMemo(index: int):
if index in memo:
return memo[index]
if index == len(s):
return 1
if s[index] == '0':
return 0
if index == len(s) - 1:
return 1
ans = recursiveWithMemo(index + 1)
if 10 <= int(s[index : index + 2]) <= 26:
ans += recursiveWithMemo(index + 2)
memo[index] = ans
return memo[index]
return recursiveWithMemo(0)