[数据结构与算法]2021-09-29 : 29号动态规划问题 组合号码

这是前几天的动态规划，因为五个月以前也做过，所以放在一起感触颇多：
组合问题
这是五个月前写的：

class Solution:
    def numDecodings(self, s: str) -> int:
        import itertools
        #动态规划试试
        dp = [0 for _ in range(len(s)+1)]
        dp[0] = 1
        for i in range(1,len(s)+1):
            if s[i-1]!='0':
                if i-2<0 or int(s[i-2]+s[i-1])>26 or int(s[i-2])==0:
                    dp[i] = dp[i-1]+0
                else:
                    dp[i] = dp[i-1]+dp[i-2]
            else:
                if i-2>=0 and 0<int(s[i-2])<=2:
                    if i-3>=0 and 10<int(s[i-3]+s[i-2])<=26:
                        dp[i] = dp[i-2]
                    else:
                        dp[i] = dp[i-1]+0
                else:
                    dp[i] = 0
                    return 0
        return dp[len(s)]

dp 弄得很难看

这是刚做的：

class Solution:
    def numDecodings(self, s: str) -> int:
        dp=[0]*(len(s)+1)
        i=0
        dp[0]=1
        while i<len(s):
            if s[i]!='0' :
                dp[i+1]+=dp[i]
            if i+2<=len(s) and s[i]!='0' and int(s[i:i+2])<=26 :
                dp[i+2]+=dp[i] 
            i+=1
        return dp[-1]

比五个月前做的好一点，做法是将dp问题和一维的字符串对应起来，以字符串的索引为基准做。分析每一个字符的状态的结果。
然后这个是答案的，大同小异，只是是以dp数组为基准：

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        f = [1] + [0] * n
        for i in range(1, n + 1):
            if s[i - 1] != '0':
                f[i] += f[i - 1]
            if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
                f[i] += f[i - 2]
        return f[n]

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/decode-ways/solution/jie-ma-fang-fa-by-leetcode-solution-p8np/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。