「题解」动态规划:解码方法
解码方法
思路:
- 状态表示
dp[i]
表示到达 i 位置时,有多少种解码方法 - 状态转移方程
根据上面的状态表示,第 i 个数字可以自己单独解码,也可以和第 i - 1 个数字一起解码,所以dp[i]
就是这两种解码方式的解码方案总和
① i 位置的数字单独解码时,如果这个数字不为0,那解码方法就有dp[i-1]
种(因为此时相当于在前面 i - 1 个数字的所有解码方案的后面再追加第 i 个数字)
如果这个数字为0,那就不能单独解码
②如果和前面的数字一起解码并且可以解码的话,那解码方法就有dp[i-2]
种(因为此时相当于在前面 i - 2 个数字的所有解码方案的后面再追加第 i - 1 和第 i 个数字)
对于①和②两种情况,如果可以解码,那就让 dp[ i ] 加上
- 初始化
因为涉及到 i - 1 和 i - 2,所以一开始得初始化 dp[0] 和 dp[1]
对于 dp[0],当第1个数字不为0时,dp[0] = 1
对于 dp[1],如果自身能解码,那 dp[1] 就是1,如果可以和前面的数字一起解码,那 dp[1] 就为2 - 填表顺序
因为得先知道前面有多少种解码方法才可以推出后面的解码方法数,所以得从左往右
填表 - 返回值
根据 dp[ i ] 的含义,我们返回dp 表最后一个元素
就可以了
class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 1) { //因为字符串长度为1时,dp[1]会越界,所以得单独讨论
if (s.charAt(0) == '0')
return 0;
else
return 1;
}
int[] dp = new int[n];
if (s.charAt(0) != '0')
dp[0] = 1;
if (dp[0] != 0) {
if (s.charAt(1) != '0') //第2个数字能单独解码
dp[1] += 1;
int t = (s.charAt(0) - '0') * 10 + s.charAt(1) - '0'; //计算两个数字结合在一起时的大小
if (t >= 10 && t <= 26) //两个数字要能解码的话,它们结合后的大小得在字母表的范围内,而且要大于10,因为 06 这种数字不能解码
dp[1] += 1;
}
for (int i = 2; i < n; i++) {
if (s.charAt(i) != '0')
dp[i] += dp[i - 1];
int tt = (s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0';
if (tt >= 10 && tt <= 26)
dp[i] += dp[i - 2];
}
return dp[n - 1];
}
}