学步园

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

//Given a string and a function : bool IsWord(const char* szBeg, const char* szEnd), use this
//function to judge whether the string can be split into seperate words.
//for example : "thisisasentence" can be split into "this is a sentence"

//pseudocode:
bool IsWord(const char* szBeg, const char* szEnd);
bool IsSplittable(const char* szString)
{
	if (*pIter == '\0') return true;

	const char* pIter = szString;
	while (*pIter != '\0')
	{
		if (IsWord(szString, pIter) && IsSplittable(pIter+1))
			return true;
		pIter++;
	}

	return false;
}

//DP version:
bool Detect(char *str)
{
	assert(str);

	int nNum = strlen(str);
	if (nNum == 0) 
		return false;

	//pRec[i] means if the sentence from position i can be cut into words
	//do this backwards
	bool* pRec = new bool[nNum+1];
	memset(pRec, 0, sizeof(bool)*nNum);
	pRec[nNum] = true;

	for (int i = nNum-1; i = 0; i--)
	{
		for (int j = i; j <= nNum-1; j++)
		{
			if (IsWord(&str[i], &str[j]) && pRec[j+1])
			{
				pRec[i] = true;
				break;
			}
		}
	}

	bool bRet = pRec[0];
	delete []pRec;

	return bRet;
}

这个题目在实际工程中经常遇到，通常的做法是把问题转化成图问题，在图中寻找路径。