推演一下 123的情况
dp[0] = 1
1--->a
dp[1] = 2, 有两种情况
1,2 拆开处理 对应 ab
12合在一起处理, 对应 l
开始推导dp[2]
1,23 对应 1w
1,2,3 拆开处理,对应 abc
12,3 3还是没跟2合体, 对应lc
可以看到,当3和2组合的时候,就是在1的基础上加上了组合后的情况。
3不和2组合的时候,就是在dp[2]的基础上加上3拆开开的情况。
我们开始推导 dp[i]
由此可见,当i既可以单独,又可以和i-1组合的时候,他的数量等于 dp[i-1] + dp[i-2]
当i不能和i-1合体的时候,dp[i] = dp[i-1] , 他只能单独处理,所以不能加上dp[i-2]
当i只能和i-1合体的时候,例如i=0,dp[i] = dp[i-2]
那么我们开始考虑特殊情况。什么情况下i 可以和i-1组合呢?
i-1 等于1的时候,3如果不为0,都可以组合,那如果3等于0呢? 那3就不能拆开处理,这个时候无法加上dp[i-1], 因此dp[i] = dp[i-2]
i-1 等于2的时候,3如果不为0, 需要在1~6的区间,才能组合,否则不能组合。
总结一下,
i和i-1既能组合又能单独出去的时候,dp[i] = dp[i-1] + dp[i-2]
i和i-1只能组合在一起的时候,dp[i] = dp[i-2]
i和i-1只能拆开处理的时候, dp[i] = dp[i-1]
按照这个思路去写就好了,将dp[0]和dp[1]特殊处理比较好理解一些。
public int solve (String nums) {
// write code here
int[] dp = new int[nums.length()];
if (nums.length() == 0 || nums.charAt(0) == '0') {
return 0;
}
if (nums.length() == 1) {
return 1;
}
dp[0] = 1;
if (nums.charAt(0) == '1') {
if (nums.charAt(1) == '0') {
dp[1] = 1;
} else {
dp[1] = 2;
}
} else if (nums.charAt(0) == '2') {
int p = Integer.parseInt(String.valueOf(nums.charAt(1)));
if (p>=0 && p<=6) {
dp[1] = 2;
} else {
dp[1] = 1;
}
} else {
if (nums.charAt(1) == '0') {
return 0;
} else {
dp[1] = 1;
}
}
for(int i=2; i<nums.length(); i++) {
//判断是否能和i-1组合起来,能组合起来就加上dp[i-2], 否则只能自己一个单独的就等于dp[i-1]
if (nums.charAt(i-1) == '1') {
if (nums.charAt(i) != '0') {
dp[i] = dp[i-2] + dp[i-1];
} else {
//只能跟i-1绑定
dp[i] = dp[i-2];
}
} else if (nums.charAt(i-1) == '2') {
int p = Integer.parseInt(String.valueOf(nums.charAt(i)));
if (p>=1 && p<=6) {
dp[i] = dp[i-2] + dp[i-1];
} else if (p == 0) {
//只能跟i-1绑定在一起
dp[i] = dp[i-2];
} else {
//只能拆开
dp[i] = dp[i-1];
}
} else {
if (nums.charAt(i) == '0') {
return 0;
} else {
dp[i] = dp[i-1];
}
}
}
return dp[nums.length()-1];
}}


京公网安备 11010502036488号