题目

一条包含字母 A-Z 的消息通过以下方式进行了编码：

  1. 'A' -> 1
  2. 'B' -> 2
  3. ...
  4. 'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

方案一（动态规划）

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == "0":
            return 0

        dp = [1] # 第 i 个位置代表输入字符中 s[:i+1] 可解码的方法的总数
        for i in range(1, len(s)):
            # 本身是不可解码的数
            if s[i] == "0":
                # 和前一个能组成一个可解码数
                if s[i-1] == "1" or s[i-1] == "2":
                    dp.append(dp[i-2])
                else: # 和前一个组不成可解码数
                    return 0
            else:
                # 和前一个可组成可解码的数
                if s[i-1] == "1" or s[i-1] == "2" and s[i] < "7":
                    dp.append(dp[i-1] + dp[i-2])
                else:
                    dp.append(dp[i-1])

        return dp[-1]

递推方程：

解码方法 - 图1%3D%5Cleft%5C%7B%0A%5Cbegin%7Baligned%7D%0Af(n-1)%20%2B%20f(n-2)%20%26%26%20s%5Bn%5D%5C%20!%3D%200%5C%20and%5C%20s%5Bn%5D%20%5C%20can%5C%20composition%5C%20valid%5C%20num%5C%20with%5C%20s%5Bn-1%5D%20%20%5C%5C%0Af(n-1)%20%26%20%26%20s%5Bn%5D%5C%20!%3D%5C%200%5C%20and%5C%20s%5Bn%5D%5C%20can’t%5C%20composition%5C%20valid%5C%20num%5C%20with%5C%20s%5Bn-1%5D%20%5C%5C%0A0%20%26%26%20s%5Bn%5D%20%3D%200%5C%20and%5C%20s%5Bn-1%5D%5C%20!%3D%20%5C%201%5C%20or%5C%202%20%5C%5C%0Af(n-2)%20%26%26%20s%5Bn%5D%20%3D%200%5C%20and%5C%20s%5Bn-1%5D%20%3D%201%5C%20or%5C%202%0A%5Cend%7Baligned%7D%0A%5Cright.#card=math&code=f%28n%29%3D%5Cleft%5C%7B%0A%5Cbegin%7Baligned%7D%0Af%28n-1%29%20%2B%20f%28n-2%29%20%26%26%20s%5Bn%5D%5C%20%21%3D%200%5C%20and%5C%20s%5Bn%5D%20%5C%20can%5C%20composition%5C%20valid%5C%20num%5C%20with%5C%20s%5Bn-1%5D%20%20%5C%5C%0Af%28n-1%29%20%26%20%26%20s%5Bn%5D%5C%20%21%3D%5C%200%5C%20and%5C%20s%5Bn%5D%5C%20can%27t%5C%20composition%5C%20valid%5C%20num%5C%20with%5C%20s%5Bn-1%5D%20%5C%5C%0A0%20%26%26%20s%5Bn%5D%20%3D%200%5C%20and%5C%20s%5Bn-1%5D%5C%20%21%3D%20%5C%201%5C%20or%5C%202%20%5C%5C%0Af%28n-2%29%20%26%26%20s%5Bn%5D%20%3D%200%5C%20and%5C%20s%5Bn-1%5D%20%3D%201%5C%20or%5C%202%0A%5Cend%7Baligned%7D%0A%5Cright.&height=80&id=55bb289a&width=623)

原文

https://leetcode-cn.com/explore/interview/card/google-interview/76/dynamic-programming/257/