【動态規劃DP，二維動歸】poj1651，Multiplication Puzzle

http://poj.org/problem?id=1651

有N張寫有數字的卡片排成一行，按一定次序從中拿走N-2張（第1張和最後一張不能拿），每次隻拿一張，取走一張卡片的同時，會得到一個分數，分值的計算方法是：要拿的卡片，和它左右兩邊的卡片，這三張卡片上數字的乘積。按不同的順序取走N-2張卡片，得到的總分可能不相同，求出給定一組卡片按上述規則拿取的最小得分。

思路，對于i，j之間的任意一個k都可能是最後一個拿走的，是以：

opt(i, j) = opt(i, k) + opt(k, j) + a[i]*a[k]*a[j], k belongs to (i, j)。

大區間以來小區間，是以從 l=3一次開始動歸。

# include<iostream>
# include<string.h>
using namespace std;

# define N 103
# define INF_MAX 10000000

int a[N],state[N][N];

int main()
{
	int i,j,k,l,n;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	memset(state,0,sizeof(state));
	for(i=1;i<=n-2;i++)
	{
		state[i][i+2]=a[i]*a[i+1]*a[i+2];
	}
	for(l=3;l<=n-1;l++)// for each length
	{
		for(i=1;i<=n-l;i++)
		{
			j=i+l;
			state[i][j]=INF_MAX;
			for(k=i+1;k<=j-1;k++)
			{
				state[i][j]= state[i][j]<state[i][k]+state[k][j]+a[i]*a[k]*a[j]? state[i][j]:state[i][k]+state[k][j]+a[i]*a[k]*a[j];
			}
		}
	}
	cout<<state[1][n]<<endl;

	return 0;
}