推演一下 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]; }
}