动态规划,考虑包含n个字符的字符串s[0,1,...,n-1]
- 如果将第一个字符单独解码,设字符串s[1,2,...,n-1]的解码方式有state1种
- 如果能将前两个字符一起解码,设字符串s[2,3,...,n-1]的解码方式有state2种
因此,可以得到一个状态转移方程:
- F(s[0,1,...,n-1]) = state1 (不能将前2个字符一起解码时)
- F(s[0,1,...,n-1]) = state1 + state2 (能将前2个字符一起解码时)
- 还有一种情况,就是如果字符串以‘0’开头,那么单独的‘0’或‘0X’这种形式都无法解码,所以F(s[0,1,...,n-1]) = 0