91. Decode Ways

https://leetcode.com/problems/decode-ways/description/

解题思路：

1. 用动态规划：状态转移方程为：if(first<=9 && first >=1) dp[i] += dp[i - 1] if(second >= 10 && second <= 26) dp[i] += dp[i-2];

代码:
class Solution {
public int numDecodings(String s) {

    if(s == null || s.length() == 0) return 0;
    int len = s.length();
    int[] dp = new int[len+1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    for(int i = 2; i <= len; i++){
        int first = Integer.valueOf(s.substring(i-1, i));
        int second = Integer.valueOf(s.substring(i-2, i));
        if(first<=9 && first >=1)
            dp[i] += dp[i-1];
        if(second >= 10 && second <= 26)
            dp[i] += dp[i-2];
    }
    return dp[len];
}

}