Decode Ways__dp__没搞定.txt

/*

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.

*/

#include <vector>
#include <string>
#include <iostream>
using namespace std;

class Solution {
public:
	int dp[5000];
	int two(char a, char b){
		int temp = (a - 0x30) * 10 + b - 0x30;
		if (temp <= 26)
			return 1;
		else return 0;
	}
	int numDecodings(string s) {
		int len = s.size();
		if (len == 0)return 0;
		//for (int i = 0; i < len; i++)
		dp[0] = 0;
		if (s[0] != '0')
			dp[1] = 1;
		else
			dp[1] = 0;
		//for (int i = 0; i < len; i++){
		for (int j = 1; j < len; j++){
			if (s[j] == '0')
				dp[j + 1] = dp[j];
			else{
				if (two(s[j - 1], s[j]))
					dp[j + 1] = dp[j - 1] + 2;
				else
					dp[j + 1] = dp[j-1] + 1;
			}
		}
		return dp[len];
	}
};

void main(){

	Solution mySolu;
	string s;
	cin >> s;
	cout << "result is : "<<mySolu.numDecodings(s);

}