# 91. Decode Ways
#### Difficulty: Medium
link: https://leetcode.com/problems/decode-ways/

### 1. Dynamic Programming
#### $O(1)$ runtime, $O(1)$ space

從字串的前面開始 decode，因為每次可以 decode 1 或 2 位的數字，剩下的字串會變成這題的子問題，只要能 decode 出至少 1 種組合，就能被考慮進去。

Q:可能有leading 0的問題，那麼"101"有幾種可能的組合呢？"1"和"01"算不算呢？還是只能是"10"和"1"這一種？
A:There is no character that is mapped to a number starting with '0'. We cannot ignore a zero when we face it while decoding. So, each '0' should be part of "10" --> 'J' or "20" --> 'T'.

DP的作法，先列出Recursive form：

##### python

<font color="#00AB5F ">Accepted</font>

###### tags: `leetcode`