91. Decode Ways

题意:

给一个由数字组成的非空字符串，1对应A，2对应B，… ，26对应Z，问这个字符串可以转换成多少种编码。

思路：动态规划

与跳台阶题的思想类似，但是对于跳一阶和跳两阶加了条件。
dp[i]表示s[0]~s[i-1]的可编码个数。
若s[i-1]属于1~9，dp[i]+=dp[i-1]
所s[i-2] s[i-1]属于1~26，dp[i]+=dp[i-2]

int numDecodings(string s) {
	if (s.empty() || s[0] == '0')
		return 0;
	if (s.size() == 1)
		return 1;

	vector<int> dp(s.size() + 1, 0);//dp[i]表示到第i位的合法编码个数（s[0]~s[i-1]）
	dp[0] = dp[1] = 1;
	for (int i = 2; i <= s.size(); ++i) {
		dp[i] = (s[i - 1] != '0' ? dp[i - 1] : 0) + ((s[i - 2] == '1' || (s[i - 2] == '2'&&s[i - 1] <= '6')) ? dp[i - 2] : 0);
	}
	return dp[s.size()];
}