题目描述
blablabla
样例
blablabla
深度优先搜索,指针 $l$ 指向字符串头的字符
- 计算去除 $l$ 指向的字符后的子字符串有多少种翻译方法
- 如果 $l$ 指向的连续两个字符能够被翻译,计算去除该两个字符后的子字符串有多少种翻译方法
class Solution {
public:
int count=0;
int getTranslationCount(string s) {
dp(s, 0, s.size()-1);
return count;
}
void dp(string s, int l, int k){
if(l>=k)
{
count++;
return;
}
if(s.substr(l,2)<="25" && s.substr(l,2)>="10") dp(s, l+2, k);
dp(s, l+1, k);
}
};
动态规划,倒推,dp[i]表示以指针i开头的子字符串有多少翻译方法。
class Solution {
public:
int getTranslationCount(string s) {
vector<int> dp(s.size()+1);
dp[s.size()-1]=1, dp[s.size()]=1;
for(int i=s.size()-2; i>=0; i--)
{
dp[i]=dp[i+1];
if(s[i]=='1' || s[i]=='2'&&s[i+1]<='5') dp[i]=dp[i+1]+dp[i+2];
}
return dp[0];
}
};
动态规划,正推,dp[i]表示以指针i结尾的子字符串有多少翻译方法。
class Solution {
public:
int getTranslationCount(string s) {
vector<int> dp(s.size());
dp[0]=1;
for(int i=1; i<s.size(); i++)
{
dp[i]=dp[i-1];
if(s[i-1]=='1' || s[i-1]=='2'&&s[i]<='5')
{
if(i==1) dp[i]=dp[i-1]+1;
else dp[i]=dp[i-1]+dp[i-2];
}
}
return dp[s.size()-1];
}
};