题解 | #把数字翻译成字符串#
把数字翻译成字符串
https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668
//这里有递归的做法和动态规划的做法参考
/*
class Solution {
public:
//表示从a的index位置开始之后有多少种译码结果
int f(string a,int index){
if(index==a.length()) return 1;
int p1=0;
//两格走
if(index+1<a.length()&&(a[index]=='1'||(a[index]=='2'&&a[index+1]<='6'))){
p1=f(a,index+2);
}
int p2=0;
if(a[index]!='0')
p2=f(a,index+1);
return p1+p2;
}
int solve(string nums) {
return f(nums,0);
}
};//递归
*/
class Solution {
public:
int solve(string nums) {
int n = nums.size();
vector<int> dp(n + 1, 0);
dp[n] = 1;
for (int i = n - 1; i >= 0; i--) {
int p1 = 0;
if (i + 1 < n && (nums[i] == '1' || (nums[i] == '2' && nums[i + 1] <= '6'))) {
p1 = dp[i + 2];
}
int p2 = 0;
if (nums[i] != '0') {
p2 = dp[i + 1];
}
dp[i] = p1 + p2;
}
return dp[0];
}
};//动态规划
查看17道真题和解析