[DP]91. Decode Ways

• 分类：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来求解