/*
動態規劃加速原理：
許多動態規劃求解問題具有類似的遞歸計算式。
設w(i,j)屬于R,1<=i<j<=n。且m(i,j)的遞歸計算式為：
m(i,i)=0,1<=i<=n
m(i,j) = w(i,j) + min{i<k<=j}{m(i,k-1)+m(k,j)},1<=i<j<=n
最優二叉搜索樹問題的動態規劃遞歸式是上述遞歸式的特殊情形/
*/
/*
O(n^3)的時間算法：

*/
void DynamicProgramming( int n, int **m, int **s, int **w )
{
	for( int i = 1; i <= n; ++i )
	{
		m[i][i] = 0;
		s[i][i] = 0;
	}

	for( int r = 1; r <= n; ++r )
	{
		for( int i = 1; i <= n - r; ++i )
		{
			int j = i + r;
			w[i][j] = weight(i,j);
			m[i][j] = m[i+1][j];
			s[i][j] = i;
			for( int k = i + 1; k < j; ++k )
			{
				int t = m[i][k] + m[k+1][j];
				if ( t <= m[i][j] )
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
			m[i][j] += w[i][j];
		}
	}
}

/*
算法需要O(n^3)計算時間和O(n^2)空間
*/

/*
四邊不等式：
在上述計算m(i,j)的遞歸式中，當函數w(i,j)滿足
w(i,j) + w(i',j') <= w(i',j) + w(i,j'),i<=i'<j<=j'
時，稱w滿足四邊形不等式。

當函數w(i,j)滿足w(i',j)<=w(i,j')，i<=i'<j<=j'時，稱w關于區間包含關系單調。
對于滿足四邊形不等式的單調函數w，可推知由遞歸式定義的函數m(i,j)
也滿足四邊形不等式，即：
m(i,j) + m(i',j') <= m(i',j) + m(i,j'),i<=i'<j<=j'
這一性質可用數學歸納法證明。我們對四邊形不等式中的“長度”l=j'-i應用數學歸納法
當i==i'或j==j'時，不等式顯然成立。由此可知，當l<=1時，函數m滿足四邊形不等式。
下面分兩種情形進行歸納證明：
情形1：i<i' = j<j
*/
/*
加速算法：
根據前面的討論，當w是滿足四邊形不等式的單調函數時
，函數s(i,j)單調，從而：
min{i<k<=j}{m(i,k-1)+m(k,j)} 
= min{s(i,j-1)<=k<=s(i+1,j)}{m(i,k-1)+m(k,j)}
*/

void SpeedDynamicProgramming( int n, int **m, int **s, int **w )
{
	for( int i = 1; i <= n; ++i )
	{
		m[i][i] = 0;
		s[i][i] = 0;
	}
	for( int r = 1; r < n; ++r )
	{
		for( int i = 1; i <= n - r; ++i )
		{
			int j = i + r;
			int i1 = s[i][j-1] > i ? s[i][j-1] : i;
			int j1 = s[i+1][j] > i ? s[i+1][j] : j - 1;
			w[i][j] = weight(i,j);
			m[i][j] = m[i][i1] + m[i1+1][j];
			s[i][j] = i1;
			for( int k = i1 + 1; k <= j1; ++k )
			{
				int t = m[i][k] + m[k+1][j];
				if ( t <= m[i][j] )
				{
					m[i][j] = t;
					s[i][j] = k;
				}
				m[i][j] += w[i][j];
			}
		}
	}
}