学步园

题目链接http://poj.org/problem?id=1651

Poj 1651 区间动态规划

#include <iostream>
using namespace std;

const int MaxNum = 0x3f3f3f3f;

int p[101] = {0};
int m[101][101] = {0};

int DP(int N,int p[])
{
	//初始化
	memset(m,0,sizeof(m));

	for (int len = 3;len <= N;len++)
	{
		for (int i = 1;i <= N - len + 1;i++)
		{
			int j = i + len - 1;

			m[i][j] = MaxNum;

			for (int k = i + 1;k < j;k++)//k表示最后取走数的下标，i 和 j不能去除
			{
				int cost = m[i][k] + m[k][j] + p[i] * p[k] * p[j];
				if (m[i][j] > cost)
				{
					m[i][j] = cost;
				}
			}
			
		}
	}
	return m[1][N];
}



int main()
{
	int N = 0;
	cin >> N;
	
	for (int i = 1;i <= N;i++)
	{
		cin >> p[i];
	}

	cout<<DP(N,p)<<endl;
	//system("pause");
	return 1;
}