思路:(区间DP 同石子合并)

• 状态表示:dp[i][j]表示切分[i,j]的最小花费
• 状态计算:枚举[i,j]之间的切点mid
  • dp[l][r] = Math.min(dp[l][r],dp[l][mid]+dp[mid+1][r]+cost)

时间复杂度(状态数量:N^2,状态转移:O(N)->O(N^3))

代码:

class Solution {
    public int minCost(int n, int[] cuts) {
        List<Integer> list = new ArrayList<>();
        for(int item : cuts){
            list.add(item);
        }
        //加入0和n避免边界条件
        list.add(0);list.add(n);
        Collections.sort(list);
        int m = list.size()-1;
        int[][] dp = new int[m+1][m+1];
        for(int len = 2 ; len <= m ; len++){
            for(int i = 1 ; i + len -1 <=m ;i++){
                int left = i,right = i + len - 1;
                dp[left][right] = Integer.MAX_VALUE;
                for(int k = left ; k <= right-1 ; k++){
                    dp[left][right] = Math.min(dp[left][right],dp[left][k]+dp[k+1][right]+list.get(right)-list.get(left-1));
                }
            }
        }
        return dp[1][m];
    }
}