题目
Problem Description
在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请设计一个程序，计算出将N堆石子合并成一堆的最小得分。
Input
输入有多组数据，每组数据第1行为一个正整数N(2<=N<=100)，以下N行，每行一个正整数，小于10000，分别表示第i堆石子的个数(1<=i<=N)。
Output
对于每组数据输出一个正整数，即最小得分
Sample Input
7
13
7
8
16
21
4
18
Sample Output
239
解题思路
| 状态: | dp[i][j] 表示第i到第j堆石子合并成一堆，所需最小力气值 |
| 状态转移方程: | dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]) 条件:i<=k<j |
| 求解： | dp[1][n] |
解题代码
//
// main.cpp
// 合并石子
//
// Created by Yeah on 14-5-13.
// Copyright (c) 2014年 Yeah. All rights reserved.
//
#include <iostream>
using namespace std;
#define min(a,b) (a < b ? a : b)
int sum[101], dp[101][101];
int main()
{
unsigned int N(0);
while (cin >> N)
{
for (unsigned int i(1); i <= N; ++i)
{
int temp;
cin >> temp;
sum[i] = sum[i - 1] + temp; //sum数组是一个前缀和数组，sum[i]代表从第1堆到第i堆石子的总数，也就是这i堆石子全部分别移动一次的代价和
}
memset(dp, 127, sizeof(dp));
for (unsigned int i(1); i <= N; ++i)
{
dp[i][i] = 0; //只有一堆的时候合并代价为0
}
for (unsigned int i(N); i != 0; --i)//i必须从后面开始一路递减，不然下面用到的dp[k + 1][j]的值无效
{
for (unsigned int j(i + 1); j <= N; ++j)
{
for (unsigned int k(i); k != j; ++k)
{
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
}
}
}
cout << dp[1][N] << endl;
}
return 0;
}