- 分类：DP
- 时间复杂度: O(n)
- 空间复杂度: O(n)
91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
代码：
DP解法：
class Solution:
def numDecodings(self, s: 'str') -> 'int':
if s==None or len(s)==0:
return 0
dp=[0 for i in range(len(s)+1)]
dp[0]=1
for i in range(1,len(s)+1):
if int(s[i-1])!=0:
dp[i]+=dp[i-1]
if i>1 and 10<=int(s[i-2:i]) and int(s[i-2:i])<=26:
dp[i]+=dp[i-2]
return dp[-1]
记忆化递归解法：
class Solution:
def numDecodings(self, s: 'str') -> 'int':
if s==None or len(s)==0:
return 0
res=self.dfs(s,0,{})
return res
def dfs(self,s,i,memo):
if (s,i) in memo:
return memo[(s,i)]
if i==len(s):
return 1
if int(s[i])==0:
return 0
res=self.dfs(s,i+1,memo)
if 10<=int(s[i:i+2]) and int(s[i:i+2])<=26:
res+=self.dfs(s,i+2,memo)
memo[(s,i)]=res
return res
讨论：
1.这道题decode way是计数类的题目，计数类的题目几乎都可以用记忆化递归和DP来求解
