动态规划一＞解码方法

/**
    1.创建dp表
    2.初始化
    3.填表
    4.返回
     */
    public int numDecodings(String ss) {
       int n = ss.length();
       int[] dp = new int[n];
       char[] s = ss.toCharArray();

       //初始化第一个位置
       if(s[0] != '0') dp[0] = 1;
       if(n == 1) return dp[0];//边界情况,只有一位字符时,放置后续越界


       /**
       初始化第二个位置：
       情况一：dp[0],和dp[1]任意一个都可以解码

       情况二：dp[0] 和 dp[1]两个可以一起解码
        */
       if(s[0] != '0' && s[1] != '0') dp[1] += 1;

       int t = (s[0] - '0')*10 + (s[1] - '0');
       if(t >= 10 && t <= 26) dp[1] += 1;

       //3.填表
       for(int i = 2; i < n; i++){

        //第一种情况：
        if(s[i] != '0') dp[i] += dp[i-1];

        //情况二：i前面的以及i搜可以编码：
        int tt = (s[i-1] - '0')*10 + (s[i] - '0');
        if(tt >= 10 && tt <= 26)  dp[i] += dp[i-2];
       }

       return dp[n-1];
    }

 public int numDecodings(String ss) {
        int n = ss.length();
       int[] dp = new int[n+1];
       char[] s = ss.toCharArray();

       dp[0] = 1;//保证后续填表是正确的

       //初始化第一个位置
       if(s[1-1] != '0') dp[1] = 1;

       //3.填表
       for(int i = 2; i <= n; i++){

        //第一种情况：
        if(s[i-1] != '0') dp[i] += dp[i-1];

        //情况二：i前面的以及i位置都可以编码：
        int tt = (s[i-2] - '0')*10 + (s[i-1] - '0');
        if(tt >= 10 && tt <= 26)  dp[i] += dp[i-2];
       }

       return dp[n];
    }