leetcode-91-解码方法（动态规划和递归两种解法）
leetcode-91-解码方法（动态规划和递归两种解法）
题目描述：
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。要完成的函数：
int numDecodings(string s)
说明：
1、这道题给定一个字符串，字符串中只含有数字，数字1可以解码为A，数字2可以解码为B……数字26可以解码为Z。
要求判断有多少种解码的方式，最终返回解码方式的个数。
比如[2,2,6]，那么可以解码为2-2-6也就是BBF，也可以解码为2-26也就是BZ，也可以解码为26-2也就是ZB。
一共三种解码方式，最终返回3。
2、这道题有两种做法，一种是动态规划，另一种是递归。
动态规划比较快，可以beats 100.00% of cpp submissions，而递归只能beats 2.67% of cpp submissions。笔者把两种做法都实现了一下，附在下文。
我们先看一下动态规划的思路，动态规划关键在于每个阶段状态的把握。
举个例子，比如12224，我们首先对第一位，只能1这种解码方法。
对第二位2，可以1-2（独立），也可以12（合并），两种解码方法。
对第三位2，可以1-2-2（独立），也可以12-2（独立），也可以1-22（合并），三种解码方法。
在这一步我们发现其实到当前位为止的解码方法个数，就是上一步的解码方法个数（在后面直接添加独立的一位）+上一步独立的个数（当然这里要判断能不能合并在一起）。
所以我们只需要记住上一步的解码方法个数和上一步的独立的个数，就可以分不同阶段去处理。
再接下来对第四位2，可以1-2-2-2，也可以12-2-2，也可以1-22-2，这三个都是直接在后面添加独立的一位，也可以1-2-22，也可以12-22，这两个就是把先前独立的一位给合并了，所以当前总的解码个数是3+2=5，当前独立的个数就是3，也是上一步的总解码个数。
过程如下：
1 | 2 | 2 | 2 | ||
|---|---|---|---|---|---|
独立可合并下一位的个数 | 1 | 1 | 2 | 3 | |
总的解码方式的个数 | 1 | 2 | 3 | 5 | |
当前例子 | 1 | 1-2 12 | 1-2-2 12-2 1-22 | 1-2-2-2 12-2 1-22-2 1-2-22 12-22 |
规律十分清晰，但我们还有一个情况没有考虑到，就是可能会出现数字0。
比如110，第二个1这一步，当前总的解码方式有1-1和11，两种，独立可合并下一位的个数有一种。
然后到了0这一步，只能合并了，于是总的解码方式变成上一步独立可合并下一位的个数1，解码方式是1-10，当前这一位的独立可合并个数清空为0。
那还有不能合并的呢，比如130，3这一步，仍然是1-3和13，总的有2种，独立的有1种。
到0这一步，不能合并，于是总的解码方式变成0，完全不能解码，返回0。
所以，构造代码如下：（附详解）
int numDecodings(string s)
{
if(s[0]=='0')return 0;//边界条件，如果第一位是字符0，那么完全不能解码，直接返回0
int t1=1,t2=1,sum1,t3;//t1表示当前独立可合并下一位的个数，t2表示当前总的解码方式的个数
for(int i=1;i<s.size();i++)//从第二位开始处理
{
sum1=(s[i-1]-'0')*10+s[i]-'0';//如果跟前一位合并，计算合并之后的数值
if(sum1>=1&&sum1<=26)//如果数值符合条件，那么可以合并
{
if(s[i]!='0')//当前位不是0，那么t2加上t1的值，t1变成原本t2的值
{
t3=t2;
t2+=t1;
t1=t3;
}
else//当前位是0，比如10这种情况，那么t2变成t1的值，t1清空
{
t2=t1;
t1=0;
}
}
else//如果计算出来不能合并
{
if(s[i]!='0')//如果当前位不是0，比如227，后面的27就不能合并，于是t2不变，t1变成t2的数值
t1=t2;
else//如果当前位是0，又不能合并，比如30这种情况，那么直接返回0
return 0;
}
}
return t2;//最终返回t2这个总的解码方式的个数
}上述代码实测0ms，beats 100.00% of cpp submissions。
如果有时间的话可以再看一下递归的做法，笔者最开始也是递归的思路，不断地试探，这种思路比较熟悉。
没时间的话就算啦，下面的文字可以直接略过。
举个例子[2,2,2,2,2]，我们先不断递归，逐个处理，直至超出范围，此时我们次数+1。
接着回退到上一层，也就是最后一个2，发现不能跟下一个数合并，于是再退到上一层，也就是倒数第二个2。
在这个时候发现可以合并，于是进入递归，但这时候下一个处理的数的位置要+2，而不是逐个处理。
接着再回退到上一层，发现第三个2和倒数第二个2可以合并，于是进入递归，这时候下一个要处理的数的位置+2，到达最后一个2那里。
……
我们可以总结出递归的操作，对于每一位而言，分两个步骤：
①进入对下一位的递归处理。
②结束①之后，判断能否与下一位合并，进入对下下位的递归处理。
所以我们可以构造出如下代码：
int count=0,t;//全局变量
void digui(string& s,int index)
{
if(index==s.size())//如果超出了范围,说明当前的尝试是成功的
{
count++;
return;
}
digui(s,index+1);//第一个步骤
t=(s[index]-'0')*10+s[index+1]-'0';//第二个步骤
if(index+1<s.size()&&t<=26&&t>=1)
digui(s,index+2);
}
int numDecodings(string s)
{
digui(s,0);
return count;
}上述代码可以解决大部分情况，但是对于0的存在无能为力。比如10，只有一种解码方式，但按照上述代码，返回结果是2。
但其实处理到0这一位的时候，当前尝试是失败的，应该结束这种尝试。
所以我们稍微修改一下代码，如下：
int count=0,t;
void digui(string& s,int index)
{
if(s[index]=='0')//增加了对于0的判断
return;
if(index==s.size())
{
count++;
return;
}
digui(s,index+1);
t=(s[index]-'0')*10+s[index+1]-'0';
if(index+1<s.size()&&t<=26&&t>=1)
digui(s,index+2);
}
int numDecodings(string s)
{
digui(s,0);
return count;
}上述代码可以通过测试，但是实测484ms，beats 2.67% of cpp submissions。递归太耗时间了。