区间dp，可以以一个区间为状态，f[i][j]是第i个切点到第j个切点的木棍的最小费用
那么对于当前这一个区间，枚举切点k，
可以得出f[i][j] = min{dp(i, k) + dp(k, j) | i < k < j} + a[j] - a[i]（这一段的长度，也就是这一刀的费用）
然后记住要人为的加入两个切点头和尾
然后因为长区间依赖于短区间，所以要从短区间渐渐推到长区间。
如果是记忆化搜索，那么就是左端点和右端点不断减少，递归，满足。
如果是递推，那么注意区间长度要不断变长，具体看代码
记忆化搜索
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 55;
int n, L, a[MAXN], f[MAXN][MAXN], vis[MAXN][MAXN];int dp(int i, int j)
{if(i + 1 == j) return 0;if(vis[i][j]) return f[i][j];vis[i][j] = 1;int& ans = f[i][j];ans = 1e9;REP(k, i + 1, j)ans = min(ans, dp(i, k) + dp(k, j) + a[j] - a[i]);return ans;
}int main()
{while(~scanf("%d%d", &L, &n) && L){REP(i, 1, n + 1) scanf("%d", &a[i]);a[0] = 0; a[n + 1] = L; memset(vis, 0, sizeof(vis));printf("The minimum cutting is %d.\n", dp(0, n + 1));} return 0;
}
递推
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 55;
int n, L, a[MAXN], f[MAXN][MAXN], vis[MAXN][MAXN];int main()
{while(~scanf("%d%d", &L, &n) && L){REP(i, 1, n + 1) scanf("%d", &a[i]);a[0] = 0; a[n + 1] = L; for(int i = n + 1; i >= 0; i--)for(int j = i + 1; j <= n + 1; j++){if(i + 1 == j) { f[i][j] = 0; continue; }f[i][j] = 1e9;REP(k, i + 1, j)f[i][j] = min(f[i][j], f[i][k] + f[k][j]+ a[j] - a[i]);}printf("The minimum cutting is %d.\n", f[0][n + 1]);} return 0;
}