题意：一根长I的棍子，要在其中的n处截断，每截断一处，就要付未截前所截棍子长度的钱，问最少需要多少钱。
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=114&problem=944
——>>设d[i][j]为只需截断第i到第j个结点用的最少钱，
遍历其中的点k（先截断结点k）,
d[i][j] = min(d[i][j], d[i][k-1] + d[k+1][j] + c[j+1] - c[i-1]);
注意边界及初始化。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 1000 + 10, INF = 1<<30;
int d[maxn][maxn], c[maxn];int dp(int i, int j)
{int& ans = d[i][j];if(ans != INF) return ans;ans = INF;for(int k = i; k <= j; k++){int L = 0, R = 0;if(k > i) L = dp(i, k-1); //注意边界if(k < j) R = dp(k+1, j); //注意边界ans = min(ans, L + R + c[j+1] - c[i-1]);}return ans;
}
int main()
{int I, n, i, j;while(~scanf("%d", &I)){if(!I) return 0;scanf("%d", &n);c[0] = 0; c[n+1] = I;for(i = 1; i <= n; i++) scanf("%d", &c[i]);for(i = 1; i <= n; i++) //初始化，重要！！！{for(j = 1; j <= n; j++)d[i][j] = INF;d[i][i] = c[i+1] - c[i-1];}printf("The minimum cutting is %d.\n", dp(1, n));}return 0;
}