91. 解码方法

题意：

解题思路：

思路：
状态定义：dp[i]代表以s[i]结尾的字符串的解码总数；
初始化：dp[0] = 1
状态转移：
1. 当s[i-1] != '0'时, s[i-1]在[1-9]中，那么可以单独把它解码成一个数字，方案数
    即dp[i] = dp[i-1]，即形成一种方案；
2. 当s[i-2] == '1' || s[i-2] == '2' && s[i-1] <= '6'时，即是s[i-2]，s[i-1]
    能组成一个两位数的编码时[10-26]，那么可以把这两位解码成一个数字，即dp[i] += dp[i-2]
3. 最后返回dp[n]

PHP代码实现：

class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function numDecodings($s) {
        $len = strlen($s);
        $dp = array_fill(0, $len + 1, 0);
        $dp[0] = 1;
        $dp[1] = $s[0] != '0' ? 1 : 0;
        for ($i = 2; $i <= $len; $i++) {
            $first = substr($s, $i - 1, 1);
            $second = substr($s, $i - 2, 2);
            if ($first >= 1 && $first <= 9) $dp[$i] += $dp[$i - 1];
            if ($second >= 10 && $second <= 26) $dp[$i] += $dp[$i - 2];
        }
        return $dp[$len];
    }
    function numDecodingsDp($s) {
        $len = strlen($s);
        $dp = array_fill(0, $len + 1, 0);
        $dp[0] = 1;
        $dp[1] = $s[0] != '0' ? 1 : 0;
        for ($i = 2; $i <= $len; $i++) {
            if ($s[$i - 1] != '0') $dp[$i] += $dp[$i - 1];
            if ($this->isValidTwoDigit($s[$i - 2], $s[$i - 1])) $dp[$i] += $dp[$i - 2];
        }
        return $dp[$len];
    }
    function isValidTwoDigit($a, $b) {
        return ($a == '1' && $b <= '9') || ($a == '2' && $b <= '6');
    }
}

class Solution {
    function numDecodings($s) {
        return $this->decode($s, 0);
    }
    function decode($c, $i) {
        if ($i == strlen($c)) return 1;
        if ($i > strlen($c)) return 0;
        $num = 0;
        if ($c[$i] != '0') $num += $this->decode($c, $i + 1);
        if ($i + 1 < strlen($c) && $this->isValidTwoDigit($c[$i], $c[$i + 1]))
            $num += $this->decode($c, $i + 2);
        return $num;
    }
    function isValidTwoDigit($a, $b) {
        return ($a == '1' && $b <= '9') || ($a == '2' && $b <= '6');
    }
}

GO代码实现：

func numDecodings(s string) int {
    n := len(s)
    if n == 0 || s[0] == '0' {
        return 0
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 1, 1
    for i := 2; i <= n; i++ {
        if s[i - 1] != '0' {
            dp[i] = dp[i - 1]
        }
        if s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '6' {
            dp[i] += dp[i - 2]
        }
    }
    return dp[n]
}