// dp[i]: 前i个字符上解码方法的总数，[0, i)
// 时间O(n), 空间O(n)
func numDecodings(s string) int {
n := len(s)
dp := make([]int, n+1)
dp[0] = 1
for i := 1; i <= n; i++ {
if s[i-1] != '0' {
dp[i] = dp[i-1]
}
if i-1 > 0 && (s[i-2] == '1' || s[i-2] == '2' && s[i-1] <= '6' && s[i-1] >= 0) {
dp[i] += dp[i-2]
}
}
return dp[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16