剑指 Offer 46. 把数字翻译成字符串 动态规划 c++

这题类似 70.爬楼梯，动态规划的思想

第 1 步：状态定义
dp[i] 表示长度为i时 有多少种翻译方法。

第 2 步：推导状态转移方程
dp[i]=dp[i−1]【+dp[i−2]】
（1）长度为i-1时若有n种方法，则如果将第i个数字单独加入，就相当于给这n个解法的末尾加一个翻译，总数n不变，所以一开始是dp[i]=dp[i−1]

（2）但要注意，加dp[i−2]是有条件的，条件就是第i个数字和第i-1个数字构成的两位数不大于25，比如是‘23’(对应’x’),此时，相当于在dp[i-2]的n个方法后面各加了一个’x’，总数n不变，所以是dp[i]+=dp[i-2]

可以看出该问题的「状态转移方程」如果（1）（2）都满足时就是dp[i]=dp[i−1]+dp[i−2]，也就是「斐波拉契数列」的通项公式。

第 3 步：思考初始化
dp[0] 无意义，它也不会被以后的计算过程参考到，因此可以不赋值或者任意赋值；
dp[1] = 1，
如果前两个数字组成的两位数小于26，那么dp[2] = 2，否则dp[2]=1，这是显然的。

第 4 步：思考输出
显然，输出为 dp[n]。

int translateNum(int num) {
	string str = to_string(num);    
	int len = str.length();

	if (len <= 1)
		return len;

	int* dp = new int[len+1];

	dp[1] = 1;
	if (stoi(str.substr(0, 2)) <= 25)
		dp[2] = 2;
	else
		dp[2] = 1;

	for (int i = 3; i <= len; ++i)
	{
		dp[i] = dp[i - 1];
		if (str[i - 2] == '0')
			continue;
		if (stoi(str.substr(i - 2, 2)) <= 25)
			dp[i] += dp[i - 2];
	}
	return dp[len];
}