1.題目描述
將a，b址遇，c熄阻，d分別編碼為1，0傲隶，10，11窃页，那么給定一個二進(jìn)制串就可以對其進(jìn)行解碼跺株。例如二進(jìn)制串“10”可以解碼為“ab”复濒，也可以解碼為“c”。給定一個二進(jìn)制串乒省，要求計(jì)算出該二進(jìn)制串有多少種解碼方式巧颈。（二進(jìn)制串的長度不超過45，能設(shè)計(jì)出O(n)復(fù)雜度的算法更佳）
2.題目解析
- 思路1：使用分治的思想
基本思路是將原二進(jìn)制串劃分成兩個規(guī)模更小的子串袖扛，求出對應(yīng)的方案數(shù)砸泛，然后相乘，就可得到原串的方案數(shù)蛆封。但這里需要注意一下唇礁，因?yàn)椤?0”有兩種解碼方案（“11”的情況類似），所以劃分子串時惨篱，如果中間恰好是“10”盏筐，則存在兩種劃分方案。
例如：“xxx10yyy”
劃分方案一：“xxx1”和“0yyy”
劃分方案二：“xxx”砸讳、“10”和“yyy”
兩種方案數(shù)之和為最終的方案數(shù)琢融。 - 思路2：
使用動態(tài)規(guī)劃的思想
假設(shè)f(i)表示前面i個字符組成的二進(jìn)制串對應(yīng)的解碼方案數(shù)，現(xiàn)在考慮第i-1個字符和第i個字
符在如下四種情況下f(i)與f(i-1)的關(guān)系簿寂。
xxxx00漾抬，00只有一種解碼方案：xxxx00，所以f(i)=f(i-1)
xxxx01常遂，01只有一種解碼方案：xxxx01纳令，所以f(i)=f(i-1)
xxxx10，10有兩種解碼方案：xxxx10和xxxx10烈钞，所以f(i)=f(i-1)+f(i-2)
xxxx11泊碑，11有兩種解碼方案：xxxx11和xxxx11，所以f(i)=f(i-1)+f(i-2)
3.參考答案
- 分治
#include <iostream>
using namespace std;
int solve(int s, int e,string& str) {
if (s >= e)
return 1;
int mid = (s + e) / 2;
if (str[mid] == '1') { // 有兩種解決方案
return solve(s, mid,str) * solve(mid + 1, e,str) +
solve(s, mid - 1,str) * solve(mid + 2, e,str);
}else{ // 有一種解決方案
return solve(s, mid,str) * solve(mid + 1, e,str);
}
}
int main(){
string str;
cin >> str;
printf("%d\n",solve(0,str.size()-1,str));
}
- 動態(tài)規(guī)劃
#include <iostream>
using namespace std;
int solve(int idx,string& str){
if (idx == -1) return 1;
if (idx == 0) return 1;
if ('0' == str[idx-1]) { // 前一個數(shù)字是0,只有一種解決方案
return solve(idx-1,str);
} else { // 前一個數(shù)字是1,有兩種解決方案
return solve(idx-1,str) + solve(idx-2,str);
}
}
int main(){
string str;
cin >> str;
printf("%d\n",solve(str.size()-1,str));
}
