题目链接
思路
这个问题与 dp 中的经典问题“跳台阶”问题十分类似，在跳台阶问题中我们是选择跳一个台阶或者两个台阶，而在这个问题中我们是选择再统计一个字符还是再统计两个字符。所以他们的状态转移方程都包含 \(dp[i]=dp[i-1]+dp[i-2]\)。
这里我们把末尾两字符的值记为 \(value\)。
只不过在跳台阶问题中我们无论怎样都能跳两个台阶，在该问题中需要满足 \(10 \leq 两个字符值 \leq 25\) 才能统计两个字符，所以取 \(dp[i-2]\) 的值是有条件的。如果不满足条件，说明这种分割方法中的 \(value\) 没法映射到对应字母，即应该舍去 \(dp[i-2]\)，此时状态方程变为 \(dp[i]=dp[i-1]\)。
综上所述，状态转移方程应该为：
\[dp[i]=\left\{
\begin{aligned}
& dp[i-1], & value <10, \\
& dp[i-1] + dp[i-2],& 10 \leq value \leq 25. \\
\end{aligned}
\right.
\]
代码
dp数组版
class Solution {
public int translateNum(int num) {
// dp[i] = dp[i - 1] + dp[i - 2]
String string = String.valueOf(num);
if(string.length() == 1){
return 1;
}
int[] dp = new int[string.length()];
dp[0] = 1;
dp[1] = Integer.valueOf(string.substring(0, 2)) > 25 ? 1 : 2;
for(int i = 2; i < string.length(); i++){
String subString = string.substring(i - 1, i + 1);
int value = Integer.valueOf(subString);
if(10 <= value && value <= 25){
dp[i] = dp[i - 1] + dp[i - 2];
}else{
dp[i] = dp[i - 1];
}
}
return dp[string.length() - 1];
}
}
空间优化版
class Solution {
public int translateNum(int num) {
// dp[i] = dp[i - 1] + dp[i - 2]
String string = String.valueOf(num);
if(string.length() == 1){
return 1;
}
int pre = 1;
int pre2 = Integer.valueOf(string.substring(0, 2)) > 25 ? 1 : 2;
int next = pre2;
for(int i = 2; i < string.length(); i++){
String subString = string.substring(i - 1, i + 1);
int value = Integer.valueOf(subString);
if(10 <= value && value <= 25){
next = pre + pre2;
}else{
next = pre2;
}
pre = pre2;
pre2 = next;
}
return next;
}
}