递归法：超时了
从字符串的后面向前计算，每一次递归都缩小子集
public class Solution {
public int NumDecodings(string s) {
return RecursiveAdd(s, s.Length - 1);
}
public int RecursiveAdd(string s, int index) {
// 已经到最后一个元素
if(index < 0)
{
return 1;
}
int count = 0;
if(s[index] != '0')
{
// 将这个元素解码为[1,9]内的数字
count = RecursiveAdd(s, index - 1);
}
// 最后一个数字
if(index == 0)
{
return count;
}
// 将元素解码为两位数
int prevIndex = index - 1;
if((s[prevIndex] == '1') || (s[prevIndex] == '2' && s[index] <= '6'))
{
count += RecursiveAdd(s, index - 2);
}
return count;
}
}参考动态规划 ：
从字符串的前面向后计算
public class Solution {
public int NumDecodings(string s) {
int len = s.Length;
// a = f[i - 2], b = f[i - 1], c = f[i]
int a = 0, b = 1, c = 0;
for(int i = 1; i <= len; i++)
{
c = 0;
if(s[i - 1] != '0')
{
c += b;
}
if(i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26))
{
c += a;
}
a = b;
b = c;
}
return c;
}
}感想：
这两种解法，刚好反映了，递归与动态规划的关系，
递归
n -> n - 1-> ...> 0
-> n - 2> ...> 0
动态规划文章来源：https://www.toymoban.com/news/detail-663190.html
0 ->1->...>n文章来源地址https://www.toymoban.com/news/detail-663190.html
到了这里，关于91. 解码方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
