91. 解码方法

https://leetcode-cn.com/problems/decode-ways/

解法一：dp

可以发现就是约束版的f(n) = f(n-1) + f(n-2);，其中如果是s[n-1]为0，f(n-1) = 0，于是f(n) = f(n-2)，因为0无法单独解码。而f(n-2)的条件则是必须在1与26之间，否则f(n) = f(n-1)。

用dp[i]表示i-1处的解码方法数

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0
        dp = [0] * (n+1)
        dp[0] = 1    #辅助，没有实际意义
        for i in range(n):
            if s[i] == '0':
                dp[i+1] = 0
            else:
                dp[i+1] = dp[i]  #f(n) = f(n-2)
            if i > 0 and (s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6')):
                dp[i+1] += dp[i-1]    #f(n) = f(n-2)+f(n-1)
        return dp[n]