Decode Ways

这道题的思路和简单的上楼梯或者叫斐波那契数列很像，但是这里多了一个条件，即如果要i - 2的值则必须满足一些条件，这些条件就是这道题比较坑的地方，首先无字符状态的答案为0，但是我们在设置DP数列时0必须设置为1，其次如果当前字符为0的话dp[i - 1]的值也是拿不到的，而要拿到dp[i - 2]的值必须满足坐标大于等于2，同时还需要这两个字符组合起来的值在10到26之间，所以这道题对两个前导状态的判定是分开的

dp[i] = 0

if s[i - 1] != '0'
    dp[i] += dp[i - 1]

if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
    dp[i] += dp[i - 2]

下面是代码

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        if not n:
            return 0

        dp = [0] * (n + 1)
        dp[0] = 1
        for i in xrange(1, n + 1):
            dp[i] = dp[i - 1] if s[i - 1] != '0' else 0
            if i >= 2 and 10 <= int(s[i - 2 : i]) <= 26:
                dp[i] += dp[i - 2]

        return dp[n]