《剑指Offer》-46-把数字翻译成字符串

读题

数字 0 ~ 25 分别对应了 a ~ z 一共 26 个字母

现在给一个数字，比如 12258，问可能对应多少种不同的翻译？

比如：1，2，2，5，8
12，2，5，8
12，25，8
1，22，5，8
1，2，25，8

一共 5 种

思路

使用动态规划的三要素：

1. 数组元素定义
2. 数组初始化
3. 状态转移方程

1225 有几种可能的翻译？
1，2，2，5
1，22，5
1，2，25
12，2，5
12，25
也是 5 种，而且可以很明显地看出，这就是 12258 对应的 5 种排列，这是因为新增的 8 对整体种数没有影响，因为 58 并不能构成一种翻译，即前一个数的末尾数字和新数字并不能够构成可能性，出现在：前末位数字是 0 / 构成的新数字 > 25

那么 122 有几种可能的翻译？
1，2，2
12，2
1，22
一共三种，对于新增的 5，与末尾数字构成的 25 会影响种数：也就是 + 除去 25 后剩下 12 可能的种数

这突然让我想到了排列组合问题，只要剔除不符合要求的数字就可以了

那这么一分析，现在我有了两个思路，1 是组合（剔除不符合要求的），2 是动态规划

动态规划

第一次提交通过的代码

	int translateNum(int num) {
		// 将一个数字按位放入一个数组中
		vector<int> nums;
		while (num > 0) {
			nums.insert(nums.begin(),num % 10);
			num /= 10;
		}
		// reverse(nums.begin(), nums.end());
		int len = nums.size();
		vector<int> dp(len+1, 1);// 多一位，0位置不使用
		for (int i = 2; i <= len; i++) {
			// 判断新数字和原本的末尾数字相加 ?>25 && 末位数字!=0
			if (nums[i-2] != 0 && (nums[i - 2] * 10 + nums[i-1]) <= 25) {
				dp[i] = dp[i - 1] + dp[i - 2];
			}
			else dp[i] = dp[i - 1];
		}
		return dp[len];
	}

这里用insert()在头位置插入可以避免使用push_back()再reverse()翻转数组

接下来我们尝试优化算法，将一维数组尝试用常数变量替代

	int translateNum(int num) {
		vector<int> nums;
		while (num > 0) {
			nums.insert(nums.begin(),num % 10);
			num /= 10;
		}
		int prepre =1, pre = 1;
		for (int i = 2; i <= nums.size(); i++) {
			if (nums[i - 2] != 0 && (nums[i - 2] * 10 + nums[i - 1]) <= 25) {
				pre = pre + prepre;
				prepre = pre - prepre;
			}
			else prepre = pre;
		}
		return pre;
	}

但是似乎并没有什么优化效果

更好的做法是，将两个循环统一并且不再使用额外的 nums 数组
这是一种逆推的做法

	int translateNum(int num) {
		int prepre = 1, pre = 1,lastDigit = num%10;
		num /= 10;

		while (num > 0) {
			int currentDigit = num % 10; // 获取当前位数字
			int combined = currentDigit * 10 + lastDigit;

			int temp = pre;
			if (combined >= 10 && combined <= 25) {
				pre += prepre;
			}
			prepre = temp;

			lastDigit = currentDigit;
			num /= 10;
		}
		return pre;
	}

ChatGPT 给出的最终优化后的代码，一开始我还很不能理解优化算法中的 prepre 和 pre，后来意识到其实从后往前推和从前往后推并没有区别，它们的种数是不会变化唯一确定的