一、题目解析
将对应字符转化为数字，我们知道有的大写字母范围是在[1，9]，剩下的则是[10，26]，这个对应关系使我们解题的关键。
二、算法原理
1.状态表示
dp[i]表示：以i位置为结尾时，解码方法总数
2.状态转移方程
根据最近的一步划分问题
3.初始化
根据状态转移方程，我们需要对dp[0]和dp[1]初始化，对于dp[0]只有1或0两种可能，而dp[i]则有三种可能0,1,2，还需要注意处理越界问题，在跑示例的时候会遇到的，这里不做过多赘述。
4.填表顺序
为了计算dp[i]我们需要知道前一个位置和前两个位置的值，所以我们需要从左向右填表。
5.返回值
我们状态表示定义dp[i]表示：以i位置为结尾，解码方法的总方法数，所以返回dp[n-1]，这里的n是给定string的长度
老规矩，根据上面的原理自己实现，链接：91. 解码方法 - 力扣（LeetCode）
三、代码示例
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
vector<int> dp(n);
dp[0] = (s[0] - '0') >= 1 && (s[0] - '0') <= 9 ? 1 : 0;//处理dp[0]
if(n<2) return dp[0];//当n<2时下面操作会越界，所以直接返回dp[0]
if(((s[0] - '0') >= 1 && (s[0] - '0') <= 9) && ((s[1]-'0') >=1 && (s[1]-'0') <=9) ) dp[1] += 1;
else dp[1] += 0;
if(((s[0] - '0')*10 + (s[1] - '0')) >=10 && ((s[0] - '0')*10 + (s[1] - '0')) <=26)//判断s[0]+s[1]能否解码
dp[1] += 1;
else dp[1] += 0;
for(int i = 2;i<n;i++)
{
if((s[i] - '0') >= 1 && (s[i] - '0') <= 9) dp[i] += dp[i-1];
else dp[i] += 0;
if(((s[i-1] - '0')*10 + (s[i] - '0')) >=10 && ((s[i-1] - '0')*10 + (s[i] - '0')) <=26)
dp[i] += dp[i-2];
else dp[i] += 0;
}
//if(dp[0] == 0) return 0;
return dp[n-1];
}
};
看到最后，如果对您有帮助还请点赞和收藏，我们下期再见！