[LeetCode]Decode Ways

很明显递归思路的题，用f(s)代表num of ways to decode string s，s[i:]代表从i开始到结尾的substring, s[:i]代表从[0, i)的substring, 那么有以下公式：

• f(s) = f(s[1:]) + f(s[2:]), if s[0] != 0, and s[:2] <= 26
• f(s) = f(s[1:]), if s[0] != 0, and s[:2] > 26
• f(s) = 0, if s[0] == 0

更具以上递归的公式我们横很容易就可以写出代码，但是有很多的重复的计算，无法过很长的test case。显然我们需要用dp来做优化，那么dp递推公式和上面是一样的。时间复杂度O(n)，空间复杂度O(n)，代码如下：