这一题我是有思路的，就是动态规划，因为昨晚上刚好看了动态规划的算法，理解也差不多，但是有一点没搞清楚，就是怎么去写状态转移方程式。这里在粗略复习一下动态规划的几个重要思想：重叠子问题，递归，缓存，无后效性，最优子结构性质
回到这一题上，思路如下：
如果字符串是空的，显然解码方式为0
如果首字符为0，那么这个字符串是无效字符串，解码为0
dp[i]表示前面长度为i的字符串的解码方式，如果s[i-2]s[i-1] 为 11-19， 21-26那么这两个字母有两种编码方式，分别占用两个字符和一个字符，如果占用两个字符，那么编码方法数与dp[i-2]相等，如果占用一个字符，那么编码方法数与dp[i-1]相等，因此，编码方法数目 = dp[i-2] +dp[i-1].
如果s[i-2][i-1]为10或者20，那么显然只有一种编码方式，占了两个字符，因此dp[i]=dp[i-2]
如果s[i-2][i-1]不满足上述情况，即有可能<10或者>26，那么只看最后一位，只要不是0,都只有一种编码方式，因此dp[i]=dp[i-1]
若最后一位为0，且前面不为1或者2，显然是不合法的输入，return 0
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return 0
if s[0] == '0':
return 0
dp = [1,1]
for i in range(2,len(s)+1):
if int(s[i-2:i]) > 10 and int(s[i-2:i]) <= 26 and int(s[i-2:i]) != 20:
dp.append(dp[i-1] + dp[i-2])
elif int(s[i-2:i]) == 10 or int(s[i-2:i]) == 20:
dp.append(dp[i-2])
elif int(s[i-1])!= 0:
dp.append(dp[i-1])
else:
return 0
return dp[-1]
