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

1. 题目

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

'A' -> 1'B' -> 2...'Z' -> 26

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

示例 1:输入: "12"输出: 2解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2:输入: "226"输出: 3解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/decode-ways

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 分类讨论，跟前面的一位能否组成有效的数字
• dp[i] 表示 以 i 位置结束的数字，有多少种可能的组合情况
  

class Solution {
   public:    int numDecodings(string s) {
           int i, n = s.size();        vector
   
     dp(n,0);        if(s[0]=='0') return 0;//首位不能是0        if(n==1) return 1;        dp[0] = 1;        if(s[0]=='1')        {
               if(s[1]=='0') dp[1]=1;            else dp[1]=2;        }        else if(s[0]=='2')        {
               if(s[1]>'0' && s[1]<='6') dp[1]=2;            else dp[1]=1;        }        else        {
               if(s[1]=='0') dp[1]=0;            else dp[1]=1;        }        for(i = 2; i < n; ++i)        {
               if(dp[i-1]==0)                return 0;//前面状态是0，不用在找了            if(s[i-1]=='0')//前面是0，0跟i-2组成数字            {
                   if(s[i] != '0')                    dp[i] = dp[i-1];//只能自己组成一个数            }            else if(s[i-1]=='1')            {
                   if(s[i]=='0') dp[i]=dp[i-2];//当前是0，0跟i-1组成数字，取dp[i-2]                else dp[i]= dp[i-1]+dp[i-2];//当前不是0，两种选择            }            else if(s[i-1]=='2')            {
                   if(s[i]>'0' && s[i]<='6') dp[i]= dp[i-1]+dp[i-2];                else if(s[i]=='0') dp[i]=dp[i-2];                else dp[i] = dp[i-1];            }            else//3-9            {
                   if(s[i]=='0') return 0;                else dp[i]=dp[i-1];            }        }        return dp[n-1];    }};
   

转载地址：https://michael.blog.csdn.net/article/details/105889570 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！