学步园

Decode Ways:

A message containing letters from A-Z is
being encoded to numbers using the following mapping:

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

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message "12",
it could be decoded as "AB" (1
2) or "L" (12).

The number of ways decoding "12" is
2.

还是一写代码还有些小问题，一是没有注意 ( l>r ) 和 ( s[l] =='0 ' ) 两个条件的返回值是不一样的，二是s[l]=='2'时才有s[l+1] <='6' 的判断，等于'1' 的时候不用，这里也没注意。

直接递归提交大数据超时，然后添加了备忘录成为DP才A掉，好久没写这种备忘录形式的DP了。。。

class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    		int n=s.length();
			if ( n==0 )
					return 0;
			vector<vector<int> > rec(n+1,vector<int>(n+1,-1));
			return solve(s,0,n-1,rec);
    }
	int solve(const string& s,int l,int r,vector<vector<int> >& rec)
	{
			int& ret=rec[l][r];
			if ( ret!=-1 )
					return ret;

			if (l>r )
				return 1;
			else if (s[l]=='0')
					return 0;
			else if (l==r)
				return 1;
			ret=solve(s,l+1,r,rec);
			if ( (s[l]=='2'&&s[l+1]<='6')
				|| (s[l]=='1') )
				ret+=solve(s,l+2,r,rec);
			return ret;
	}
};

有递归形式的DP，当然就有递推形式的DP咯，而且递推形式的空间只需要O(n)，其实递归的也可以弄成O(n)。

class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    		int n=s.length();
			if ( n==0 )
					return 0;
			vector<int>  dp(n+1,0);
			dp[n]=1;
			dp[n-1]=s[n-1]=='0'?0:1;
			for(int i=n-2;i>=0;i--)
			{
					if ( s[i]=='0' )
					{
							dp[i]=0;
							continue;
					}
					dp[i]=dp[i+1];
					if ( s[i]=='1'|| (s[i]=='2'&&s[i+1]<='6'))
							dp[i]+=dp[i+2];
			}
			return dp[0];
    }
};