题意

字母A对应1，以此类推，Z对应26。给定一个字符串，里面只包含0-9，可能存在前导0。求可以解码为多少种字符串。

例如112可以解码为1,1,2 → AAB, 11,2 → KB, 1,12 → AL. 一共三种。

思路

这道题还是dp的一种，考虑的点就是，我们每次新处理一个数字字符的时候，有如下几种情况

以112这个字符串为例。

• 直接被追加到当前字符串的结尾

  例如 我们已经处理了11这个字符串, 可能的编码包括，1,1 → AA, 11 → K. 目前在处理2这个字符，我们可以直接直接将2放到已经形成的排列之后，例如 1,1,2 → AAB, 11,2 → KB.

  对于前一个字符是0的情况，只能追加到结尾，因为06这种是不合理的。

• 第二种情况。当前字符与前面的字符组合

  同理当我们出列11这个字符串后，2是可以与前面的1进行组合的，那么就是1, 12 → AL的情况。

所以状态转移为

dp[i] += dp[i-1] 无限制

dp[i] += dp[i-2] ：如果当前字符可以与s[i-1]进行组合。

实现代码如下

func numDecodings(s string) int {
	l := len(s)
	dp := make([]int, l)
	if s[0] == '0' {
		return 0
	}
	dp[0] = 1
	for idx := 1; idx < l; idx++ {
		if s[idx] == '0' {
			if s[idx-1] != '1' && s[idx-1] != '2' {
				return 0
			}
			i := idx - 2
			if i < 0 {
				i = 0
			}
			dp[idx] = dp[i]
			continue
		}

		dp[idx] = dp[idx-1]
		if s[idx-1] == '0' {
			continue
		}
		if (s[idx-1] == '1') || s[idx-1] == '2' && s[idx] >= '1' && s[idx] <= '6' {
			i := idx - 2
			if i < 0 {
				i = 0
			}
			dp[idx] += dp[i]
		}
	}

	return dp[l-1]
}