91. 解码方法

这算是昨天做的题了，总结一下，醍醐灌顶，对于动态规划问题，在前几天博客中我已经进行了总结，发现我掌握的只是个别题的做法，没有领悟精髓，今天再一看，真的感触很多，我们对待动态规划问题，想一想每一步的各种情况，也就是每个子问题的各种情况，与上一个子问题的联系等等！一定要找好状态转换方程！下面列出题目：

我们发现，所有的问题都在怎么去找子问题上，这种题目一般都是后面的字符与前面的字符有啥联系呢，下面我们看这个题，我们写在纸上会发现有两种模式，226  我们发现如果22可以形成二种（2,2和22）那么我们需要找第一个2之前的状态，也就是说dp[i+1]=dp[i]+dp[i-1],怎么来的就不说啦，就是提醒自己，一定要找转换方程，把每一步好好想一想。下面列出代码：

    public int numDecodings(String s) {
        if(s.length()==0||s.equals("")) return  0;
        int[] dp=new int[s.length()+1];
        if(s.charAt(0)=='0') return 0;
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<dp.length;i++){
            if(s.charAt(i-1)=='0'&&(s.charAt(i-2)!='1'&&s.charAt(i-2)!='2')) return 0;
            if(s.charAt(i-2)=='1'||(s.charAt(i-2)=='2'&&s.charAt(i-1)-'0'<=6)){
                if(s.charAt(i-1)=='0'){
                    dp[i]=dp[i-2];
                    continue;
                }
                dp[i]=dp[i-1]+dp[i-2];
            }
            else {
                dp[i]=dp[i-1];
            }
            System.out.println(dp[i]+"  ");
        }
        return dp[dp.length-1];
    }

边界记得处理一下就行了