力扣 -- 91.解码方法-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣 -- 91.解码方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣 -- 91.解码方法,力扣动态规划,力扣经典面试题,leetcode,算法,职场和发展,c++,动态规划

题目链接：91. 解码方法 - 力扣（LeetCode）

以下是用动态规划的思想解决这道题目，如果对动态规划五部曲的含义还不是很清楚的老铁可以看看本专栏的第一题动规(10条消息) 力扣 -- 746. 使用最小花费爬楼梯_KOBE 0824 BRYANT的博客-CSDN博客，这里有比较详细的解析动态规划五部曲的含义的，相信各位小伙伴都能看懂并且掌握这道题的。

力扣 -- 91.解码方法,力扣动态规划,力扣经典面试题,leetcode,算法,职场和发展,c++,动态规划

参考代码：

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        //多开一个虚拟节点
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=s[0]!='0';
        //如果s只有一个元素，那么应该直接返回
        if(n<2)
        {
            return dp[1];
        }
        //因为dp[0]和dp[1]已经填过了，所以从dp[2]开始填，因为多开了一个虚拟节点，所以应该填到dp[n]
        for(int i=2;i<=n;i++)
        {
            //这里写s[i-1]是调整了下标的映射关系，所有需要找s[i]的地方都要在原来的下标基础上减1
            //第一种情况
            if(s[i-1]!='0')
            {
                dp[i]+=dp[i-1];
            }
            int tmp=10*(s[i-2]-'0')+(s[i-1]-'0');
            //第二种情况
            if(tmp>=10&&tmp<=26)
            {
                dp[i]+=dp[i-2];
            }
        }
        return dp[n];
    }
};

以上就是分析这道dp题目的整个过程，虽然确实有点复杂，但是一步一步地分析，还是可以学明白的，加油，相信自己，动规是可以学会的。

你学会了吗？如果以上题解对你有所帮助，那么就点亮以下小心心呗，点点关注呗，后期还会持续更新动态规划的经典题目哦，我们下期见！！！！！文章来源地址https://www.toymoban.com/news/detail-522550.html

到了这里，关于力扣 -- 91.解码方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！