给定一个数字,我们按照如下规则把它翻译为字符串:0翻译成“a”,1翻译成“b”,……,25翻译成“z”。一个数字可能有多种翻译。例如,12258有5种不同的翻译,分别是“bccfi”、“bwfi”、“bczi”、“mcfi”、“mzi”。求一个数字有多少种不同的翻译方法?
解题思路
- 回溯法(暴力枚举)
- 动态规划(回溯法可以减少递归次数)
上代码(C++香)
法一:回溯法,很easy
int countN = 0;
// 回溯法
void dfs(int num[], int n, int index){
if(index == n){
countN++;
return ;
}
// 如果当前值是1,并且后面至少还有1位数
if((num[index] == 1) && (index < n - 1))
dfs(num, n, index + 2);
// 如果当前值是2,并且后面至少还有1位数,并且下一位小于6
else if((num[index] == 2) && (index < n - 1) && (num[index + 1] < 6))
dfs(num, n, index + 2);
// 也可以只走一步
dfs(num, n, index + 1);
}
法二:动态规划
找到状态转移方程:\(f(i)=f(i+1)+g*f(i+2)\),其中当第i位数字和第i+1两位数字拼接起来的数字在10~25之间时,g为1,否则为0。
int GetTranslationCount(const string& number)
{
int length = number.length();
int* counts = new int[length];
int count = 0;
// 倒推
for(int i = length - 1; i >= 0; --i)
{
count = 0;
if(i < length - 1)
count = counts[i + 1];
else
count = 1;
if(i < length - 1)
{
int digit1 = number[i] - '0';
int digit2 = number[i + 1] - '0';
int converted = digit1 * 10 + digit2;
if(converted >= 10 && converted <= 25)
{
if(i < length - 2)
// 加上上面的判断就是count = count[i + 1] + count[i + 2]
count += counts[i + 2];
else
// i = length - 2,即倒数第二位就有两种方法
count += 1;
}
}
counts[i] = count;
}
count = counts[0];
delete[] counts;
return count;
}
int GetTranslationCount(int number)
{
if(number < 0)
return 0;
string numberInString = to_string(number);
return GetTranslationCount(numberInString);
}