题目链接：https://cn.vjudge.net/problem/UVA-10003
题意：给出一根长为L的木棍，给出长为n的c数组,c[i]代表在木棍的长为c[i]处为一个切割点，每次切割的木棍的长度为花费，让选择切点的顺序，使得费用最小。
很好的dp题，题解来自：https://www.cnblogs.com/simplekinght/p/6953258.html
思路：这道题与最优矩阵连乘的思想一样，那就是分析最优子结构，再根据子结构来定义状态，首先我们假定第一次分割的最优方案是在k处分割，得到0~k与k~L两段木棍，那么如何最优分割0~k与0~L就是它的子问题，我们根据子问题定义状态d(i,j)是分割从割点i到割点j的最优方案，状态转移方程 d(i,j)=min{d(i,k)+d(k,j)+(cut[j]-cut[i])}(其中i<k<j)，接下来是确定边界，d(i,i)=0 和 d(i,i+1)=0，并注意赋初值INF
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxN=55;
const ll INF=0x7f;int L,n,c[maxN],ans;
int dp[maxN][maxN];//dp(i,j)是分割从割点i到割点j的最优方案
bool vis[maxN][maxN];int fdp(int i,int j)
{if((j-i)<=1) return 0;if(vis[i][j]==true) return dp[i][j];vis[i][j]=true;for(int k=i+1;k<j;k++)dp[i][j]=min(dp[i][j],fdp(i,k)+fdp(k,j)+(c[j]-c[i]));return dp[i][j];
}int main()
{while(scanf("%d",&L)&&L){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&c[i]);c[0]=0;c[n+1]=L;memset(dp,0x7f,sizeof(dp));memset(vis,0,sizeof(vis));printf("The minimum cutting is %d.\n",fdp(0,n+1));}return 0;
}