这道题每个数字有两种情况:一种是和前面一个数字合并表示一个字母,一种是独立表示一个字母。因此它的状态为dp[i][2]。转移的时候要注意两种情况:当独立表示字母时,如果当前数字为0,则不可以独立表示字母。当合并表示字母时,当前一个数字加自己的数字大于26,也不可以合并表示字母。初始状态dp[0][0]为1,dp[0][1]为0。剩下的就很简单了:
public int numDecodings(String s) {
char[] chars = s.toCharArray();
if(chars[0] == '0'){
return 0;
}
int[][] dp = new int[chars.length][2];
dp[0][0] = 1;
dp[0][1] = 0;
for(int i = 1 ; i < chars.length ; i++){
if(chars[i] == '0'){
dp[i][0] = 0;
}else{
dp[i][0] = dp[i-1][0] + dp[i-1][1];
}
if((chars[i-1] - '0')*10 + (chars[i]-'0') > 26){
dp[i][1] = 0;
}else{
dp[i][1] = dp[i-1][0];
}
}
return (dp[chars.length-1][0] + dp[chars.length-1][1]);
}