动态规划： 力扣91. 解码方法

1、题目描述

2、题解：

方法：动态规划：

动态规划问题，弄清楚三点：

1、重复子问题；
2、最优子结构；
3、无后效性。
动态规划：

1、状态定义；
2、状态转移方程；
3、初始化；base case
4、输出；
5、思考状态压缩。
可以用递归去求，但是会存在重叠子问题，加个备忘录可以解决重复问题。

状态定义： dp[i] 为以str[i]结尾前缀子串的解码数
状态转移方程：
        （1）若s[i] != '0'：
                dp[i] = dp[i - 1]
            解释：s[i]  被唯一译码
        （2）s[i-1] = '1':d[i] += dp[i - 2]
初始化：
    dp[0,...,n-1] = 0
    dp[0] = 1
输出：
    dp[n - 1]

python 代码如下：

class Solution:
    def numDecodings(self, s: str) -> int:
        # #动态规划
        n = len(s)
        if not s:
            return 0
        dp = [0] * n
        if s[0] == '0':
            return 0
        dp[0] = 1
        for i in range(1,n):
            if s[i] != '0':
                dp[i] = dp[i - 1]
            num = 10 * (ord(s[i - 1]) - ord('0')) + (ord(s[i]) - ord('0'))
            if 10 <= num <= 26:
            # if '10' <= s[i-1:i+1] <= '26':
                if i == 1:
                    dp[i] += 1
                else:
                    dp[i] += dp[i - 2]
        return dp[n - 1]

3、复杂度分析：

时间复杂度：O(n），n为字符串的长度
空间复杂度：O(n)