/*
**	Dynamic Programming
**	ways[i] means the ways for decoding from ith character to the end of the string
**  then we could have formula as below:
**	
**	ways[i] =
**				0 						when s[i] = '0'
**				ways[i+1]				when s[i] and s[i+1] could not combinate to a valid decoding
**				ways[i+1] + ways[i+2]	otherwise
*/


#include <iostream>

using namespace std;

int NumDecodings(string s) 
{
	int len = s.length();
	if (len == 0) return 0;

	int ways[len+1];
	//this value is set for easy calculation for last two numbers
	ways[len] = 1; 

	//the ways decoding for last number
	ways[len-1] = s[len-1] == '0'? 0 : 1; 

	for (int i = len-2; i >= 0; --i)
	{
		char c0 = s[i];
		if(c0 == '0')
		{
			ways[i] = 0;
			continue;
		}

		//decode current number only
		ways[i] = ways[i+1];

		//decode with next number to be two
		char c1 = s[i+1];
		//valid two numbers decoding
		if (c0 == '1' 
			|| (c0 == '0' && c1 != '0') 
			|| (c0 == '2' && c1 <= '6'))
			ways[i] += ways[i+2];

		//We could know that when we get countinious 0s, the final result would be 0
		// if (ways[i] == 0 && ways[i+1] == 0)
		// {
		// 	ways[0] = 0;
		// 	break;
		// }
	}
	return ways[0];
}


int main(int argc, char** argv)
{
	cout << NumDecodings("11");
	cout << NumDecodings("43719");
	return 0;
}