dp数组，单变量

题目

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

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

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

题目数据保证答案肯定是一个 32 位的整数。

示例1：

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

示例2：

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

示例3：

输入：s = "0"
输出：0

示例4：

输入：s = "1"
输出：1

示例5：

输入：s = "2"
输出：1

注：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

题解

算法分析：

  • 利用动态规划进行处理，如下情况讨论：
    • dp[i]为str[0..i]的译码方法总数
    • 分情况讨论：（建立最优子结构）
      • 若s[i]=‘0’，若s[i-1]=‘1’or ‘2’，则dp[i]=dp[i-2]；否则return 0

        解释：s[i-1]+s[i]唯一被译码，不增加情况

      • 若s[i-1]=‘1’，则dp[i]=dp[i-1]+dp[i-2]

        解释：s[i-1]与s[i]分开译码，为dp[i-1]；合并译码，为dp[i-2]

      • 若s[i-1]=‘2’且‘1’<=s[i]<=‘6’，则dp[i]=dp[i-1]+dp[i-2]

        解释：同上

    • 由分析可知，dp[i]仅可能与前两项有关，故可以用单变量代替dp[]数组，将空间复杂度从O(n)降到O(1)

方法一：dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0]=='0':
            return 0
        dp =[0 for i in range(len(s))]
        dp[0]=1
        dp[-1]=1
        for i in range(1,len(s)):
            if s[i]=='0':
                if s[i-1]=='1' or s[i-1]=='2':
                    dp[i]=dp[i-2]
                else:
                    return 0
            else:
                if (s[i - 1] == '1' or (s[i - 1] == '2' and  s[i] >= '1' and s[i] <= '6')):
                    dp[i]=dp[i-1]+dp[i-2]
                else:
                    dp[i]=dp[i-1]
        return dp[-1]
1
2
3
4
a= Solution()
s="1201234"
result=a.numDecodings(s)
print(result)
3

方法二：单变量代替dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0]=='0':
            return 0
        pre=1
        cur=1 # pre=dp[-1]=1  cur=dp[0]=1
        for i in range(1,len(s)):
            tmp=cur
            if s[i]=='0':
                if s[i-1]=='1' or s[i-1]=='2':
                    cur = pre
                else:
                    return 0
            else:
                if (s[i - 1] == '1' or (s[i - 1] == '2' and  s[i] >= '1' and s[i] <= '6')):
                    cur = cur +pre
            pre=tmp
        return cur
1
2
3
4
a= Solution()
s="1201234"
result=a.numDecodings(s)
print(result)
3

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2020/12/13/LeetCode-C-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-91.%20%E8%A7%A3%E7%A0%81%E6%96%B9%E6%B3%95/