Leetcode 91 Decode Ways

思路

序列型动态规划。类似与上楼梯的题目。根据题目描述，设定dp[i]为前i个字符有几种解码方式。由于第i个字符可以由前i-2个字符加上后两位【后两位解析成一个字符】或者前i-1个字符加上最后一位而来。
因此状态转移方程为dp[i]=dp[i-1](最后一位不是0)+dp[i-2](最后两位组成的数字在10～26之间，因为A只能解析成1而不是01)
边界条件：dp[0]=1

代码

class Solution {
    public int numDecodings(String s) {
    int[] dp = new int[s.length()+1];dp[0] = 1;for(int i = 1; i <= s.length(); i++) {
    if(s.charAt(i-1) != '0')dp[i] += dp[i-1];if(i-2 >= 0) {
    int lastNum = Integer.parseInt(s.substring(i-2,i));if(lastNum >= 10 && lastNum <= 26)dp[i] += dp[i-2];}}return dp[s.length()];}
}

复杂度分析

时间复杂度O(n), 空间复杂度O(n)