题解 | #把数字翻译成字符串#
把数字翻译成字符串
https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668
2022.0816算法第32题把数字翻译成字符串
这题也是采用动态规划进行求解，但是状态转移方程就不是特别好想了。
1、状态矩阵
dp表示字符串i个位置可能的翻译方法。
vector<int> dp(nums.size()+1,1);2、初始状态
初始状态需要考虑的比较多，
dp[0]=1,dp[1]=1;
if(nums=="0")
return 0;
if(nums=="10"||nums=="20")
return 1;
for(int i=1;i<nums.size();i++){
if(nums[i]=='0'&&nums[i-1]!='1'&&nums[i-1]!='2')
return 0;
}
3、状态转移方程
这个状态转移方程也是比较复杂，情况比较多，需要考虑的很细，要确保数字在11-19和21-26之间，包括两边.
if((nums[i-2]=='1'&&nums[i-1]!='0')||
(nums[i-2]=='2'&&nums[i-1]>'0'&&nums[i-1]<'7')){
dp[i]=dp[i-1]+dp[i-2];
}
else{
dp[i]=dp[i-1];
}
我刚开始没想到需要和前两项构成关系，只考虑前一项是不行的。
第i项的值，在满足数字在11-19和21-26之间时，为
dp[i-1]+dp[i-2]主要就是这时候需要考虑两种情况。
但不满足11-19和21-26之间时，
dp[i]=dp[i-1];情况就不会变多。
觉着挺难的。
Momenta公司福利 286人发布
