LeetCode剑指offer46把数字翻译成字符串（动态规划） _剑指offer

学向勤中得，萤窗万卷书。这篇文章主要讲述LeetCode剑指offer46把数字翻译成字符串（动态规划）相关的知识，希望能为你提供帮助。

一、题目
二、思路字母只有26个英文字母，数字上不超过2位数，本题本质上就是青蛙跳阶梯类型（数字可以是一位，或者两位），只不过需要赋值前进行判断。
（1）确定状态
???dp[i]???表示前??i??个数字的翻译方法可能个数。
（2）转移方程

只有两种情况可以进行组合翻译：

前一个数字为1是，则必然满足[10,25]区间，可以和当前数字组合翻译
若前一个数组为2，且当前数字< =5，则满足[10,25]区间，可以组合翻译

而如果是单独翻译，则翻译方法数不变：??dp[i] = dp[i - 1]??。

（3）初始条件+边界
???dp[1] = 1???没有问题，因为只有一个数字则肯定只有一种翻译方法，但是为了??dp[2]???计算中，如果当前两个数字能组合翻译时，是??dp[2] = dp[1] + dp[0]???，这种情况的??dp[2]???应该为2，为了配合这个，我们需要设置??dp[0] = 1??。
（4）计算顺序
从小到大。
三、代码

class Solution
public:
int translateNum(int num)
if(num < 10)
return 1;

string strnum = to_string(num);
vector< int> dp(strnum.size() + 1);
//当前两个数字能组合翻译时，dp[2] = dp[1] + dp[0],
//d[2]结果应该是2，dp[1]已知等于1，所以dp[0]也等于1
dp[0] = 1;
//一个数字只有一种翻译方法
dp[1] = 1;
for(int i = 2; i < = strnum.size(); i++)
if(strnum[i - 2] == 1 ||
(strnum[i - 2] == 2 & & strnum[i - 1] < = 5))
dp[i] = dp[i - 1] + dp[i - 2];
else
//否则是单独翻译
dp[i] = dp[i - 1];

return dp[strnum.size()];

;