91. Decode Ways

# Medium

Dynamic Programming

dp[i] 表示前i个元素有多少种拆分方法

看起来简单，但很不容易写对，要注意以下四点

1. "1000"当前数字为零，返回0

2. "127" 因为27>26，不能组合在一起

3. "120" 其中20必须组合在一起

4. “130” 其中30不能组合在一起，则拆分成3和0，回归到情况1

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0 for i in range(len(s)+1)]
        dp[0] = 1
        
        for i in range(len(s)):
            if s[i] == '0':
                dp[i+1] = 0
            else:
                dp[i+1] = dp[i]
            
            # the condition must be like this
            # eg, '10001', '01', '27', '30'
            if i >= 1 and ((s[i-1] == '1') or (s[i-1] == '2' and s[i] <= '6')):
                dp[i+1] += dp[i-1]
        return dp[-1]

必须要跟上面的代码写得一模一样，不然就会出错，DP能够处理更大的数据。由于dp[i]最多只取决于dp[i-1] 和 dp[i-2]，时间复杂度为 $O(n)$,由于只使用了dp这个 数组，所以空间复杂度为 $O(n)$