題目鏈接
難度：中等 ??????類型： 字符串、動態(tài)規(guī)劃
一條包含字母 A-Z 的消息通過以下方式進行了編碼：
'A' -> 1
'B' -> 2
...
'Z' -> 26
給定一個只包含數(shù)字的非空字符串，請計算解碼方法的總數(shù)。
示例1
輸入: "12"
輸出: 2
解釋: 它可以解碼為 "AB"（1 2）或者 "L"（12）。
示例2
輸入: "226"
輸出: 3
解釋: 它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
解題思路
dp[i]表示到第i-1位時解碼的方法數(shù)
兩種情況：
1.s[i-1]單獨解碼，方法數(shù)為dp[i-1]
2.s[i-2:i]拼接成雙字符解碼，若10<=s[i-2:i]<26，雙字符合格，解碼的方法數(shù)位dp[i-2]，否則為0
綜合兩種情況，得到狀態(tài)轉(zhuǎn)移矩陣：
dp[i] = dp[i-1] + (dp[i-2] if 雙字符合格 else 0)
為什么dp[i]表示的使i-1位？
例如 216，在判斷第二位‘1’時，i-2<0了，狀態(tài)轉(zhuǎn)移矩陣不能用了，故在前加一位，即dp[0]為1
代碼實現(xiàn)
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1 if s[0]!='0' else 0
for i in range(2,n+1):
if s[i-1]!='0':
dp[i] = dp[i-1]
if 9< int(s[i-2:i])<27:
dp[i] += dp[i-2]
return dp[-1]
