动态规划算法基本要素.cpp

算法分析部分

/*
动态规划算法的有效性依赖于问题本身所具有的两个重要性质
（1）最优子结构
（2）子问题重叠性质
一般意义上讲，问题所具有的这两个重要性质是该问题可以用动态规划算法
求解的基本要素。
*/

/*
最优子结构：
当问题的最优解包含了子问题的最优解时，该问题具有最优子结构性质。
问题的最优子结构性质，是可用动态规划算法的重要线索

在分析问题的最优子结构时，首先我们假设由问题的最优解导出的其子问题的
解不是最优的，然后再说明这个假设可以导出一个比原问题更优的解，从而导
出矛盾

在动态规划算法中，问题的最优子结构性质使我们能够以自底向上的方式递归地从
子问题的最优解逐步构造出整个问题的最优解。同时也能够使我们在相对较小的
子问题空间内考虑问题。
*/

/*
重叠子问题：
可用动态规划算法求解的问题应该具备的另一个基本要素是子问题的重叠性质，
在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些
子问题被反复计算多次。动态规划算法正式利用这种子问题重叠的性质，对每个
子问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，只要简单地花
常数时间查一下就好了。通常，不同的子问题个数随输入问题的大小呈多项式增长。因此
动态规划算法通常只需要多项式时间
*/

/*
备忘录算法：
动态规划的一个变形是备忘录方法，也就是用一个表格来保存已经解决的子问题的答案
，下次需要解此子问题时，只要简单地查看该子问题的答案，而不必重新计算。与动态规划
算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。
因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为
每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
备忘录方法为每个子问题建立一个记录项，初始化时记录项存入一个特殊的值，表示该子问题
尚未求解。在求解过程中，对每个待求的子问题，首先查看其相应的记录项。若记录项存储的是
初始化时存入的特殊值，则表示该子问题是第一次遇到，则此时计算出该子问题的解，并保存在其
相应的记录项中。若记录项中存储的已不是初始化时存入的特殊值，则表示该子问题已被计算过，
其相应的记录项中。若记录项中存储的已不是初始化时存入的特殊值，则表示该子问题已被计算过
，其相应的记录项中存储的是该子问题的解答。此时，只要从记录项中取出该子问题的解答即可。

*/

/*
下面的算法MemoizedMatrixChain是解矩阵连乘积最优计算次序问题的备忘录方法
*/

int LookupChain( int i, int j )
{
	if ( m[i][j] > 0 )
	{
		return m[i][j];
	}
	if ( i == j )
	{
		return 0;
	}
	int u = LookupChain( i,i ) + LookupChain( i + 1,j ) + p[i-1]*p[i]*p[j];
	s[i][j] = i;
	for( int k = i + 1; k < j; ++k )
	{
		int t = LookupChain( i,k ) + LookupChain( k + 1,j ) + p[i-1]*p[k]*p[j];
		if ( t < u )
		{
			u = t;
			s[i][j] = k;
		}
	}
	m[i][j] = u;
	return u;
}

int MemoizedMatrixChain( int n, int **m, int **s )
{
	for( int i = 1; i <= n; ++i )
	{
		for( int j = i; j <= n; ++j )
		{
			m[i][j] = 0;
		}
	}
	
	return LookupChain( 1, n );
}

int main()
{
	return 0;
}

/*
综上所述，矩阵连乘积的最优计算次序问题可用自顶向下的备忘录算法和自底向上的动态规划算法
在O(n^3)计算时间内求解。这两个算法都利用了子问题重叠性质。总共有O(n^2)个不同的子问题。
对每个子问题来说，两种方法只解一次，并记录答案。再次遇到该子问题时，简单地取已经得到的
答案，节省计算量，提高效率。

一般来讲，当一个问题的所有子问题都至少要解一次的时候，则用动态规划算法比用备忘录算法好。
此时，动态规划算法没有任何多余的计算，还可利用其规则的表格存取方式，来减少在动态规划算法中
的计算时间和空间需求。当子问题空间中的部分子问题可不必求解时，用备忘录方法则较有利，
因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题

*/