动态规划之解码方法【LeetCode】

动态规划之解码方法

• 91. 解码方法
• • 解法1
  • 解法2

    91. 解码方法

    91. 解码方法

    

    解法1

    状态表示（这是最重要的）：dp[i]表示以第i个字符为结尾，解码方法的总数。

    状态转移方程（最难的）：根据最近的一步来划分问题，从右向左思考，我们需要考虑s[i]和s[i-1]是单独为一个字符形成两个数字，还是合并为一个字符形成为一个数字。

      如果s[i]和s[i-1]是单独为一个字符形成两个数字，那么dp[i]的值就是dp[i-1]的值；

      如果s[i]和s[i-1]合并为一个字符形成为一个数字，那么dp[i]的值就是dp[i-2]的值。因为s[i]和s[i-1]都形成一个数字了，再dp[i]往前就是就是dp[i-2]了。

      因为单独一个0不能解码，所以当s[i]和s[i-1]是单独为一个字符时，若s[i]为’0’，dp[i] = 0;

      如果形成的两位数数字不在[10, 26]区间内的话（因为前导0不能编码，所以不是[1, 26]），所以当s[i]和s[i-1]合并为一个字符时，若超出这个范围了，dp[i] = 0;

    初始化：因为我们得状态转移方程里面包含dp[i-1]和dp[i-2]，所以我们需要初始化dp[0], dp[1]，以免越界及无法计算。dp[0]就只有一个,我们只需要判断它是不是不为’0’即可，dp[0] = s[0] != '0';。

      dp[1]的话有两种情况，单独为两个数1且分开成两个数，单独为一个数需要判断形成的这一个数是否在[10, 26]这个范围里面；分别为两个数只需要判断s[0]和s[1]是不是都不为’0’。

    填表顺序：当我们求解当前问题时，需要知道所需较小子问题的解，这就需要我们先求解得到较小子问题的解，这就是填表顺序。我们这道解法是从左向右填表。

    返回值：return dp[n-1];

    代码实现：

    class Solution {
    public:
        int numDecodings(string s) {
            // 创建dp表
            int n = s.size();
            vector dp(n);
            // 初始化
            dp[0] = s[0] != '0';
            // 处理边界问题
            if(1 == n) return dp[0];
            if(s[0] != '0' && s[1] != '0') dp[1] = 1;
            int count = (s[0]-'0')*10 + s[1]-'0';
            if(count >= 10 && count 
                if(s[i] != '0') dp[i] += dp[i-1];
                int count1 = (s[i-1]-'0')*10 + s[i]-'0';
                if(count1 = 10 && count1 
    public:
        int numDecodings(string s) {
            // 创建dp表
            int n = s.size();
            vector
                if(s[i-1] != '0') dp[i] += dp[i-1];
                int count1 = (s[i-2]-'0')*10 + s[i-1]-'0';
                if(count1 = 10 && count1 
    public:
        int numDecodings(string s) {
            // 创建dp表
            int n = s.size();
            vector
                if(s[i-1] != '0') dp[i] += dp[i-1];
                int count1 = (s[i-2]-'0')*10 + s[i-1]-'0';
                if(count1 = 10 && count1