leetcode 91 解码方法 （动态规划，python）

leetcode 91 解码方法 （动态规划，python）

转载：https://blog.csdn.net/yangjingjing9/article/details/77036563

【思路】

本题宜用动态规划：

共有三种情况：

l s[i-2]和s[i-1] 两个字符是10----26之间但不包括10和20这两个数时，有两种编码方式，比如23------>[“BC”，“W”]，所以dp[i] = dp[i-1]+dp[i-2]

l s[i-2]和s[i-1] 两个字符10或20这两个数时，有一种编码方式，比如10------>[“J”], 所以dp[i] = dp[i-2]

l s[i-2]和s[i-1] 两个字符不在上述两种范围时，编码方式为零，比如27，比如01，所以dp[i] = dp[i-1]

【Python实现】

# -*- coding: utf-8 -*-
"""
Created on Thu Aug 10 09:22:16 2017
 
@author: Administrator
"""
 
class Solution(object):
    def numDecodings(self, s):
       """
       :type s: str
       :rtype: int
       """
       if s=="" or s[0]=='0': return 0
       dp=[1,1]
       for i in range(2,len(s)+1):
           if 10 <=int(s[i-2:i]) <=26 and s[i-1]!='0':#编码方式为2
                dp.append(dp[i-1]+dp[i-2])
           elif int(s[i-2:i])==10 or int(s[i-2:i])==20:#编码方式为1
                dp.append(dp[i-2])
           elif s[i-1]!='0':#编码方式为0
                dp.append(dp[i-1])
           else:
                return 0
       #print(dp[len(s)])
       return dp[len(s)]
 
 
if __name__ == '__main__':
   S= Solution()
    s= "1220"
   S.numDecodings(s)