---
# System prepended metadata

title: 1547. Minimum Cost to Cut a Stick
tags: [Leetcode, Dynamic Programming, Hard]

---

# 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]的问题。所以状态转移方程是：
```dp[i][j] = min{dp[i][k]+dp[k][j]+cuts[j]-cuts[i]} for k=i+1,i+2,...,j-1```
边界条件是对于任何长度为1的区间[i,i+1]，不需要下刀，代价就是0.
## Code
```java=
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];
    }
}
```