基于斐波那契数列衍生的动态规划问题
关联问题:
剑指offer10-I, 斐波那契数列
剑指offer10-II, 青蛙跳台阶
C++ 代码
class Solution {
public:
int translateNum(int num) {
string str = to_string(num);
int len = str.size();
int q[len + 1];
q[0] = 1, q[1] = 1;//q[0] == 1是由q(2) == 2逆推出的
for(int i = 2; i <= len; i ++){
int cur = (str[i - 2] - '0') * 10 + (str[i - 1] - '0');//注意i表示的是q的索引
//对应的str索引要再减去1
if(cur >= 10 && cur < 26)//若str[i - 2] - '0') * 10 + (str[i - 1] - '0'有意义
q[i] = q[i - 1] + q[i - 2];
else
q[i] = q[i - 1];
}
return q[len];
}
};