划分型动态规划——解码方法

左手的ㄟ右手 2022-10-27 12:06 170阅读 0赞

#  #

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

‘A’ -> 1  
‘B’ -> 2  
…  
‘Z’ -> 26  
给定一个只包含数字的非空字符串，请计算解码方法的总数。题目数据保证答案肯定是一个 32 位的整数。

**示例 1：**

输入：s = "12"
    输出：2
    解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
    示例 2：

### 1、题目分析 ###

从题目的提问方式能够很明显的看出这是一个技术类型的动态规划。

### 2、确定状态 ###

解密数字串即划分成若干数字，每段数字对应一个字母。

最后一步（最后一段）：对应一个字母，最后一个字母可能会对应两个数字，因为字母对应的数字1-26，从10之后就是两位数字。

因此如果需要解密N个字符的解密方式数，需要知道数字串前N-1和N-2个字符的解密方式数。

所以我们可以假设f\[i\]表示数字串S前i个数字解密成字母串的方式数。

### 3、转移方程 ###

假设f\[i\]表示数字串S前i个数字解密成字母串的方式数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

### 4、初始条件和边界情况 ###

初始条件：f\[0\]=1，即空串有一种解密方式

边界情况：如果i=1，只看最后一个数字

### 5、计算顺序 ###

从小到大的方式

答案是f\[N\]

时间复杂度O(N)，空间复杂度O(N)

### 6、代码实现 ###

class Solution:
        def numDecodings(self, s: str) -> int:
            if len(s)==0:
                return 
            for i in range(len(s)):
                if i!='0':
                    s=s[i:]
                    break
            dp = [0 for i in range(len(s)+1)]
            if len(s)==0:
                return
            dp[0]=1
            for i in range(len(s)+1):
                if s[i-1] in "123456789":#python没有char类型，不能用s[i-1]-'0'
                    dp[i]+=dp[i-1]
                if i>1:
                    j = (int(s[i-2]))*10 + int(s[i-1])#新学会的强制转换，或者int(s[i:i+2])
                    if j<=26 and j>=10:
                        dp[i]+=dp[i-2]
            return dp[len(s)]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/7411a64fe72f4029ac5a2e6ef7f2226d.png