# 1547. Minimum Cost to Cut a Stick
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-cost-to-cut-a-stick/
## 思路
这是一道典型的区间型的DP。对于[i,j]这段区间，我们考虑如何砍下第一刀？显然下刀的位置可以是cuts[i+1],cuts[i+2],...,cuts[j-1]。我们假设在位置k下刀，那么这一刀的代价就是[i,j]的程度，接下来问题就转为了两个小区间[i,k]和[k,j]的问题。所以状态转移方程是：

边界条件是对于任何长度为1的区间[i,i+1]，不需要下刀，代价就是0.
## Code

class Solution {
public int minCost(int n, int[] cuts) {
Arrays.sort(cuts);
int m = cuts.length;
int[] arr = new int[m+2];
arr[m+1] = n;
for(int i=0; i<m; i++) arr[i+1] = cuts[i];

int[][] dp = new int[m+2][m+2];
for(int len=3; len<=m+2; len++){
for(int i=0; i+len-1<=m+1; i++){
int j = i+len-1;
dp[i][j] = Integer.MAX_VALUE;
for(int k=i+1; k<=j-1; k++){
dp[i][j] = Math.min(dp[i][j], arr[j]-arr[i]+dp[i][k]+dp[k][j]);
}
}
}
return dp[0][m+1];
}
}