AcWing 59. 把数字翻译成字符串(dp,自写)
原题链接
中等
作者:
逸误
,
2024-04-05 17:23:35
,
所有人可见
,
阅读 5
//dp的关键都是:保证不重不漏!
//f[i][0]:前i个字母,第i个单独翻译的方案数,f[i][1]:第i个和i-1结合的方案数
//状态划分(为了能够转移而划分):
//把前i个字母的总翻译方案数划分为:前i个字母,第i个单独翻译的方案数+第i个和i-1个组合的方案数(即f[i][0]+f[i][1])
//对于前者,一定可以单独翻译,方案数为第i-1个字母的总方案数,即f[i][0]=f[i-1][0]+f[i-1][1]
//对于后者,如果满足条件,方案数为第i-1个字母单独选择时的方案数,即f[i][1]=f[i-1][0]
class Solution {
public:
int getTranslationCount(string s) {
int f[105][2]={0};
int n=s.size();
f[0][0]=1;//第0个字母,单独翻译有1种翻译方法
for(int i=1;i<n;i++)
{
f[i][0]=f[i-1][0]+f[i-1][1];//总是可以单独翻译的
if(('0'<=s[i]&&s[i]<='5'&&s[i-1]=='2')||s[i-1]=='1')//可以和前面那个字母组合翻译
f[i][1]=f[i-1][0];
}
return f[n-1][0]+f[n-1][1];
}
};