※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: 91. Decode Ways
: 该题提供一个由数字组成的字串s，并提供我们一个编码表：
: 'A' -> "1"
: 'B' -> "2"
: ...
: 'Z' -> "26"
: 求出s共有几种编码的方式，若无法被编码出来返回0。
: Example：
: Input: s = "12"
: Output: 2
: Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
思路:
1.爬楼梯的变化版 爬楼梯就是给你阶梯长度 你一次能爬一阶或两阶 问你有几种爬法
问就是 f(n) = f(n-1) + f(n-2), f(0) = f(1) = 1
2.所以这题也是差不多 一次选一个数字或两个数字 只是要多检查合不合法
dp[i] = dp[i+1] + dp[i+2] dp[i]代表从i往下的字串有几种 decode 方法
如果自己是0 -> 不能 decode 0开头的数字 一定不合法 爬法是0
如果自己是1~9 -> 一次选一个的操作合法 可以加上dp[i+1]
如果自己和下一个 < 27 -> 一次选两个的操作合法 可以加上dp[i+2]
3.dp要加长一下 写起来比较方便
因为在算dp[len(s)-2] 的时候 没有dp[len(s)]给你加
简单判断掉也可以
Python code:
class Solution:
def numDecodings(self, s: str) -> int:
dp = [0]*(len(s)+1)
dp[-1], dp[-2] = 1, 0 if s[-1] == '0' else 1
for i in range(len(s)-2, -1, -1):
if s[i] == '0':
dp[i] = 0
else:
dp[i] = dp[i+1] + (dp[i+2] if int(s[i:i+2]) < 27 else 0)
return dp[0]