剑指 Offer 46. 把数字翻译成字符串

剑指 Offer 46. 把数字翻译成字符串

题目

传送门

解题思路(简单动态规划)

动态规划方程。
先数字转化成字符串s = 12325664866处理
令s[i - 2]和s[i - 1]所组成的数字为 t
当t小于10或者大于25时只有一种情况。
当t属于$[10,25]$时,这是两个字符串可以拆开

• 例如当t == 12时,1 和 2可以分别组成字符
• 例如当t == 28时,2 和 8不可以分别组成字符

  转移方程

  $dp(x) = dp(x-1) + dp(x -2)$ 当t >= 10 && t <= 25
  $dp(x) = dp(x-1)$ 当t < 10 || t > 25

代码 let me see see your code

class Solution {
public:
    int translateNum(int num) {

if(num < 10) {return 1;}

        string s = to_string(num);
        int len = s.length();
        vector<int> dp(len + 1);
        dp[1] = 1; // 显而易见 dp[1] = 1
        dp[0] = 1; // 比如 num = 12，有两种方法，即 dp[2] = dp[1] + dp[0]，可得 dp[0] = 1

        for(int i = 2; i < len + 1; ++i) {
            int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if (t < 10 || t > 25) dp[i] = dp[i - 1];
            else dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[len];
    }
};