來源：LeetCode第91題

難度：中等

描述：一條包含字母A-Z的消息通過以下映射進行了編碼:
'A'->1,'B'->2,'z'->26,要接嗎已編碼的消息，所有數字必須基于上述映射的方法，反向映射回字母(可能由多種方法)，例如"11106"可以映射成'AAJF',將消息分組為(1 1 10 6),注意，消息不能分組為(1 11 06)因為06不能映射成F，這是因為'6'和'06'在映射中并不等價。
示例1：
輸入：s="12";
輸出：2
解釋：他可以解碼為"AB"(1 2)或者"L"(12);

第一種求解方法：遞歸

//定義一個遞歸函數，String s表述輸入的字符串，index表示開始進行判斷的索引
public int numDecode(String s,int index)
{
//當索引大于s.length()的時候，表明已經找到了一個路徑返回1，這是作為遞歸的終止條件if(index>=s.length())
return 1;int res=0;
if(s.charAt(index)!='0')
{
//這個判斷標準表明s.chaeAt(index)可以作為單獨的一個字母，從而可繼續向下走
res+=numDecode(s,index+1);
}
//以'1'開頭或以2開頭且第二個字母小于6(26)，兩者均要滿足下一個字母存在
if(((index+1)<=s.length()-1)&&(s.charAt(index)=='1'||(s.charAt(index)=='2'&&s.charAt(index+1)<='6')))
{
res+=numDecode(s,index+2);
}
map[index]=res;
return res;
}

在進行遞歸操作的時候，很多情況下會出現重復計算，從而可以使用一個map實現計算過得值的一個存儲，從而使得不用進行重復計算，
?

public int numDecode(String s,int index,int []map)
{
if(index>=s.length())
return 1;
int res=0;
if(map[index]!=-1)
{
return res+map[index];
}
if(s.charAt(index)!='0')
{
res+=numDecode(s,index+1,map);
}
if((index+1<=s.length()-1)&&((s.charAt(index)=='1')||(s.charAt(index)=='2'||(s.charAt(index+1)<='6'))))
{
res+=numDecode(s,Index+2,map);
}
}
public void NumDecode(String s)
{
int []map=new int [s.length()];
numDecode(s,0,map);
}

動態規劃求解，除此之外，還可以使用動態規劃進行求解，每一次可以走一步也可以走兩步
?

public int numDecode3(String s,int index)
{
int dp[]=new int[s.length()];
if(s.charAt(0)=='0')
{
dp[0]=0
}else
{
dp[0]=1;
}
for(int i=1;i<s.length();i++)
{
if(s.charAt(i)!='0')
{
dp[i]=dp[i-1]
}else
{
dp[i]=0;
}
if(i>=2)
{
if((i+1<=s.length()-1)&&((s.charAt(i)=='1')||(s.charAt(i)=='2'&&s.charAt(i+1)<='6')))
{
dp[i]+=dp[i-2];
}
}
}
return dp[s.length()-1]
}