剑指 Offer 46. 把数字翻译成字符串 发表于 2022-04-25 DP12345678910111213141516171819202122class Solution { public int translateNum(int num) { String str = String.valueOf(num); // 定义 dp[i] 为第 i 个字符结尾的数字的方案数,此时 i 从 1 开始 int[] dp = new int[str.length() + 1]; dp[0] = 1; dp[1] = 1; // 此处注意 i 从 1 开始,故访问 str 时需要减去 1 for (int i = 2; i <= str.length(); i++) { char x = str.charAt(i - 2), y = str.charAt(i - 1); if (x == '1' || (x == '2' && y <= '5')) { dp[i] = dp[i - 1] + dp[i - 2]; } else { dp[i] = dp[i - 1]; } } return dp[str.length()]; }} DP12345678910111213141516171819202122class Solution { public int translateNum(int num) { String numStr = String.valueOf(num); // 定义 dp[i] 表示截止至 numStr[i] 的翻译方法数 int[] dp = new int[numStr.length()]; dp[0] = 1; for (int i = 1; i < numStr.length(); i++) { // 作为一个字符进行翻译时 dp[i] += dp[i - 1]; // 作为两个字符进行翻译时,'10' -> '25' char p = numStr.charAt(i - 1), c = numStr.charAt(i); if (p == '1' || (p == '2' && (c >= '0' && c <= '5'))) { dp[i] += i - 2 >= 0 ? dp[i - 2] : 1; } } return dp[numStr.length() - 1]; }} Reference剑指 Offer 46. 把数字翻译成字符串