剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode）
求组合数，先将数字转化为字符串，最多会有两个字符被连接起来进行翻译，考虑当前字符i，如果 i-1和i可以连接起来翻译，那么f[i] = f[i-1] + f[i-2]，否则f[i] = f[i-1]。
class Solution { public: int translateNum(int num) { string s = to_string(num); vector<int> dp(s.size()+1, 0); dp[0] = 1; dp[1] = 1; for(int i = 2; i <= s.size(); ++i){ if(s[i-2] == '0' || s[i-2] > '2' || (s[i-2] == '2' && s[i-1] > '5')) dp[i] = dp[i-1]; else{ dp[i] = dp[i-1] + dp[i-2]; } } //for(const auto &c : dp) cout << c << " "; return dp[s.size()]; } };也不难看出从左到右dp和从右到左dp都是可行的
可以进行空间压缩，但没必要。。。
字符串只是进行辅助操作的，不用其实也可以，因为相应的数字取余取整就可以获取到。
