本文共 1647 字，大约阅读时间需要 5 分钟。

链接：

大意：

给定一个非空字符串s，s中的字符仅为'0'-'9'。定义一种加密规则：'A'->1,'B'->2,...,'Z'->26。要求出s有多少种解密方法。例子：

思路：

动态规划。

定义两个整型数组dan，shuang。dan[i] : 第i个数字单一解密时子串s0-si有多少种解密方法；shuang[i] : 第i个数字和第i - 1个数字组合解密时子串s0-si有多少种解密方法。

如果第i个数字仅能单一解密，即第i个数字和第i-1个数字的组合大于26，则dan[i] = dan[i - 1] + shuang[i - 1],shuang[i] = 0。

如果第i个数字仅能与第i-1个数字组合解密，即第i个数字为0且与第i-1个数字的组合为10或者20，则dan[i] = 0,shuang[i] = dan[i - 1]。此时有两种情况可以直接返回0：如果出现了连续的两个0（即第i - 1个数字也是0）或者与第i - 1个数字的组合大于26（即为30，40，50...）

如果第i个数字既能与第i-1个数字组合解密，也能单独解密。则dan[i] = dan[i - 1] + shuang[i - 1],shuang[i] = dan[i - 1]

以上的文字描述就是递推关系。

代码：

class Solution {    public int numDecodings(String s) {        char[] cs = s.toCharArray();        // dan[i]:第i个数字为单时有多少种可能 shuang[i]:第i个数字和第i-1个数字组合为双时有多少种可能        int[] dan = new int[cs.length], shuang = new int[cs.length];        int i = 1;        if (cs[0] == '0')            return 0;        dan[0] = 1;        shuang[0] = 0;        while (i < cs.length) {            if (cs[i] == '0') { // 第i个数字只能和第i-1个数字组合为双的情况                // 当出现连续的两个0或者第i-1个数字和第i个数字的组合大于26时直接返回0                if (cs[i - 1] == '0' || (cs[i - 1] - '0') * 10 + (cs[i] - '0') > 26)                     return 0;                dan[i] = 0;                shuang[i] = dan[i - 1];            } else if ((cs[i - 1] - '0') * 10 + (cs[i] - '0') > 26){ // 第i个数字只能为单的情况                dan[i] = dan[i - 1] + shuang[i - 1];                shuang[i] = 0;            } else { // 第i个数字既可以为单也可以和第i-1个数字为双                dan[i] = dan[i - 1] + shuang[i - 1];                shuang[i] = dan[i - 1];            }            i++;        }        return dan[cs.length - 1] + shuang[cs.length - 1];    }}

结果：

结论：

很巧妙的一个动归题，说到底还是找递推关系。 

转载地址：http://ptesi.baihongyu.com/