###### tags: `Leetcode` `medium` `dynamic programming` `python`

# 91. Decode Ways

## [題目連結:] https://leetcode.com/problems/decode-ways/

## 題目:
A message containing letters from ```A-Z``` can be **encoded** into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To **decode** an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, ```"11106"``` can be mapped into:
* ```"AAJF"``` with the grouping ```(1 1 10 6)```
* ```"KJF"``` with the grouping ```(11 10 6)```

Note that the grouping ```(1 11 06)``` is invalid because ```"06"``` cannot be mapped into ```'F'``` since ```"6"``` is different from ```"06"```.

Given a string s containing only digits, return the **number** of ways to **decode** it.

The test cases are generated so that the answer fits in a **32-bit** integer.

**Example 1:**

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

**Example 2:**

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

**Example 3:**

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

## 解題想法:
* 題目為，給一數字，求其可以表示的解碼組合數
* 使用DP:
* 定義dp[i]: 前i個數字字元的組合總數，dp[len(s)]即為所求
* init: dp[0]=1 沒有數字，一種組合
* dp[i]=dp[i-1]+dp[i-2]
* 相當於上階梯，可以每次上一階or兩階
* case1: 當前數字自己視為一個字母(自己不能為'0')->總組合數與dp[i-1]一樣
* case2: (當前數字自己+前一個數子)視為一個字母->總組合數與dp[i-2]一樣
* 額外注意，因為以0為起始不可構成任何字串，所以要確認前一個數字是否為0

ex: s='226'
22: 可以decode為 2，2->BB or 22->V 
在考慮6時:
case1: 可以6自己視為字符，所以總數繼承dp[i-1]
case2: 可以與前面一數進行組合，
因為 s[i-2](2)!=0 且 s[i-2]+s[i-1]<=26
所以26可以編碼為Z
所以可以繼承dp[i-2]
所以最終dp[i]=dp[i-1]+dp[i-2]=3

## Python:

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i]:前i個字元的組合總數
        n = len(s)
        dp = [0]*(n+1)
        dp[0]=1
        for i in range(1,len(dp)):
            if s[i-1]!='0':
                dp[i]+=dp[i-1]
            if i>1 and s[i-2]!='0' and int(s[i-2]+s[i-1])<=26:
                dp[i]+=dp[i-2]
        return dp[n]

result = Solution()
ans = result.numDecodings("226")
print(ans)