学步园

http://haixiaoyang.wordpress.com/category/dynamic-programming/

/*
get all possibilities of letter combinations
a->1, b->2, ...., z->26
so for "112" it returns 3, which are
1,1,2 => aab
11,2 => kb
1,12 => al
*/

int _inner_ways(const char* pStr)
{
	if (*pStr == 0) 
		return 1;
	if (*pStr <= '0' || *pStr > '9')
		return 0;

	int n = _inner_ways(pStr+1);
	if ((*pStr == '1' && *(pStr + 1) >= '0' && *(pStr + 1) <= '9') 
		|| (*pStr == '2' && *(pStr + 1) >= '0' && *(pStr + 1) <= '6'))
		n += _inner_ways(pStr+2);

	return n;
}

int GetWays(const char* pStr)
{
	if (NULL == pStr || *pStr == 0)
		return 0;

	return _inner_ways(pStr);
}

int GetWaysDP(const char* pStr)
{
	if (NULL == pStr || *pStr == 0)
		return 0;

	int nLen = strlen(pStr);
	int nTmp2 = 1;
	int nTmp1 = 0;

	if (pStr[nLen-1] > '0' && pStr[nLen-1] <= '9')
		nTmp1 = 1;

	int nRes = nTmp1;
	for (int i = nLen-2; i >= 0; i--)
	{
		int nTmp = 0;
		if (pStr[i] > '0' && pStr[i] <= '9')
			nTmp += nTmp1;
		if ((pStr[i] == '1' && pStr[i+1] >= '0' && pStr[i+1] <= '9') || 
			(pStr[i] == '2' && pStr[i+1] >= '0' && pStr[i+1] <= '6'))
			nTmp += nTmp2;

		nRes = nTmp;
		nTmp2 = nTmp1;
		nTmp1 = nRes;
	}

	return nRes;
}

第一种方法是递归，但是递归明显有很多重复计算

第二种方法是动态规划，这里dp是从右向左的