Leetcode 91. 解码方法 动态规划

原题链接：Leetcode 91. 解码方法


自己写的代码：

class Solution {
public:int numDecodings(string s) {int n=s.size();vector<int> dp(n,1);if(s[n-1]=='0') dp[n-1]=0;for(int i=n-2;i>=0;i--){if(s[i]!='0'){string t=s.substr(i,2);int tmp=atoi(t.c_str());if(tmp>=1&&tmp<=26) dp[i]=dp[i+1]+(i+2<n ? dp[i+2]:1);else dp[i]=dp[i+1];}else {if(i-1>=0 && (s[i-1]=='1' || s[i-1]=='2')){dp[i]=0;dp[i-1]=dp[i+1];i--;}else return 0;}}return dp[0];}
};

参考别人的代码：Leecode 91. 解码方法

class Solution {
public:int numDecodings(string s) {int n=s.size();if(s[0]=='0') return 0;int res=1,pre=1;for(int i=1;i<n;i++){int tmp=res;if(s[i]=='0'){if(s[i-1]=='1' || s[i-1]=='2') res=pre;else return 0;}else if(s[i-1]=='1' || (s[i-1]=='2' && s[i]>='1' && s[i]<='6'))res+=pre;pre=tmp;}return res;}
};