本文主要是介绍动态规划-leetcode#91-解码方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
class Solution {
public:int numDecodings(string s) {if(s.length()==0) return 0;vector<int> dp(s.length(),0);if(s[0]-'0'>=1 && s[0]-'0'<=26)//错误（1）数字中可能出现0dp[0]=1;else return 0;for(int i=1;i<s.length();i++){int sum = 0;if(s[i]-'0'>=1 && s[i]-'0'<=26)//同上sum+=dp[i-1];if(s.length()-i>=1 && s[i-1]!='0' && stoi(s.substr(i-1,2))<=26 && stoi(s.substr(i-1,2))>=1)//错误（2）二位数不能以0开头sum+=i-2>=0?dp[i-2]:1;//前两位数+1，前面没有dp[i-2],其余的加dp[i-2]dp[i]=sum;}return dp[s.length()-1];}};动态规划，举例12120，遍历每一个位置i，dp[i]存到i截止的所有字符串的解码方法数，那么dp[i-1]以及之前的解都求好了，现在考虑dp[i],如果以s[i]分解，那么解法就是dp[i-1]，如果以s[i-1~i]分解，也就是两位数字，那么首先比如在1到26区间内并且s[i-1]不能等于0，如果可以分解，那么解法就是dp[i-2],这里要注意边界条件，如果i-2小于0了，那+1。
- 这题要注意考虑0数字的特殊性~
- c++里面：sting 转int可以用 stoi(string)；int转string用to_string(int)
这篇关于动态规划-leetcode#91-解码方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
