1. 概述

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

题目数据保证答案肯定是一个 32 位的整数。

示例 1：

输入：s = “12”

输出：2

解释：它可以解码为 “AB”（1 2）或者 “L”（12）。

示例 2：

输入：s = “226”

输出：3

解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 3：

输入：s = “0”

输出：0

示例 4：

输入：s = “1”

输出：1

示例 5：

输入：s = “2”

输出：1

提示：

1 <= s.length <= 100

s 只包含数字，并且可能包含前导零。

1.1 思路

1. 本题使用动态规划思路，没当 s 多加一位，则当前可以解码数量是前面的数量加1 或 2，理由如下：
   1. 因为这个数本身一定有对应的解码字母对应
   2. 或者与前一个数，构成一个对应字母

所以，一定是加1 或 2。

公式：
f[i] = f[i - 1] + 1 + (substr(str, -2) < 27 ? 1 : 0)

2. 解题

<?php
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    public function numDecodings(string $s) {
        $len = strlen($s);
        // 前i个数的解法数量
        $f[1] = 1;
        for ($i = 2; $i < $len; $i++) {
            $f[$i] = $f[$i - 1] + 1;
            if ($len < 2) {
                continue;
            }
            $len2 = $s[$i - 1] . $s[$i];
            if ($len2 <= 26) {
                $f[$i]++;
            }
        }
        return $f[$len - 1];
    }
}
$s = '226';
$cls = new Solution();
$ret = $cls->numDecodings($s);
print_r($ret);