原题传送门—>>

题目描述：

A message containing letters from A-Z is being encoded to numbers using the following mapping:

  • ‘A’ -> 1
  • ‘B’ -> 2
  • …
  • ‘Z’ -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

示例1：

  • Input: s = “12”
  • Output: 2
  • Explanation: It could be decoded as “AB” (1 2) or “L” (12).

示例2：

  • Input: s = “226”
  • Output: 3
  • Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

示例3：

  • Input: s = “0”
  • Output: 0
  • Explanation: There is no character that is mapped to a number starting with ‘0’. We cannot ignore a zero when we face it while decoding. So, each ‘0’ should be part of “10” —> ‘J’ or “20” —> ‘T’.

示例4：

  • Input: s = “1”
  • Output: 1

注：

  • <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

入门级的dp+分治。但这方面的题我做的确实不太多…

dp:
对于仅包含’1’ ‘2’ 的字符串:
“1” : 1种编码方式
“12”：2种编码方式
“111”：3种编码方式
其实就是dp的入门题“爬楼梯”.假设长度为n的12串为steps[n] 则steps[n] = steps[n - 1] + steps[n - 2];

为方便描述，现规定:对于编码“5”,5被称为“单”，对于编码“12”，1称作“头”，2称作“尾”。
显然，1、2可作单、可做头、可作尾，因而1、2字符串可以直接dp

分治:
当字符串中出现0、3、4…7、8这些字符时，可以发现，0只能作尾,其他字符只能作尾或作单。
也就是说，当字符串是“121312”，3是不可能和后面的1混合编码的，那么可以将”1213”和”12”分开考虑，实际上”121312”的答案是”1213”与”12”的乘积。类推：”171921012319101”可以看成”17” “19” “210” “123” “19” “101”几个子串。
而对于子串而言，末尾数字也需要分三种情况：”0”自成一类，”3~6”是一类，”7~9”是一类。

100%kill代码：

class Solution {
public:
    int steps[102];
    int numDecodings(string s) {
        if(s[0] == '0')
            return 0;
        steps[0] = 1;
        steps[1] = 1;
        steps[2] = 2;
        for(int i = 3; i < 46; ++i)//为什么是46呢，因为47就超过int型上限了。。。按理，题目给的长度其实最大是100,这个只能自己试了
        {
            steps[i] = steps[i - 1] + steps[i - 2];
        }//建立dp数组
        vector<char> tmp;
        int ans = 1;
    for(int i = 0; i < s.size(); ++i)
    {
        tmp.push_back(s[i]);
        if((s[i] < '1')||(s[i] > '2'))
        {
            ans *= count(tmp);
            tmp.clear();
        }
    }

        return ans*steps[tmp.size()];
    }
    int count(vector<char>& str)//这是处理子串的函数
    {
        int sum = 0;
        if(str.back() == '0')//对于0
        {
            if(str.size() == 1)
                return 0;
            else
                return steps[str.size() - 2];

        }
        if(str.back() > '6')//d对于7、8、9
        {
            if(str.size() == 1)
                return 1;
            if(str[str.size()-2] == '1')
                return steps[str.size()];
            return steps[str.size()-1];//只能单着了
        }
        //剩下3、4、5、6
        return steps[str.size()];

    }
};