5486. 切棍子的最小成本

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的最小总成本。

解题思路：

这题看起来是找最佳切割顺序，有一定误导性；其实这道题和高楼扔鸡蛋很相似。
根据因为最多只需要切 100次，所有我们可以采用分治的思想。将复杂问题转化为一个个的子问题，递归求解。
因为总得切一刀，第一次先随意选一个切割点。然后找出第一刀所有可行解的最优解。

递推公式：

dp[i][j] 表示 cuts[i] ~ cutsj,这些切割点，所有切割顺序的最优解。
F(i,j) = min{ F(i,i) + F(i+1, j), ..., F(i,x) + F(x+1,j), ..., F(i,j-1) + F(j, j) } + 当前这一刀的cost

class Solution {
    #define INF 1e9
    // dp[102][102];
    vector<vector<int>> dp;
public:
    inline int getCost(int wooden_start, int wooden_end, int cut){
        if(cut > wooden_start && cut < wooden_end){
            return wooden_end - wooden_start;
        }
        return 0;
    }
    // dp[i][j] 表示 cuts[i] ~ cuts[j](不含cuts[j]),这些切割点的最优解
    // F(i,j) =  min{ F(i,i) + F(i+1, j), ..., F(i,x) + F(x+1,j), ..., F(i,j-1) + F(j, j)} + 当前这一刀的cost
    int solve(int i, int j, vector<int>& cuts, int wooden_start, int wooden_end){
        if (i >= j) {
            return 0;
        }
        // 直接返回结果
        if(dp[i][j] >= 0) {
            return dp[i][j];
        }
        // 首次随意选一个点,切下去
        int ans = INF;
        for(int x = i; x < j; ++x) {
            int pos = cuts[x];
            int cur_cost = getCost(wooden_start, wooden_end, pos);
            int tmp = solve(i, x, cuts, wooden_start, pos) + solve(x+1, j, cuts, pos, wooden_end);
            ans = std::min(ans, tmp + cur_cost);
        }
        dp[i][j] = ans;
        // printf("dp[%d][%d] = %d \n", i, j , dp[i][j]);
        return ans;
    }
    int minCost(int n, vector<int>& cuts) {
        sort(cuts.begin(), cuts.end());
        int len = cuts.size();
        dp = vector<vector<int>>(len+2, vector<int>(len+2, -1));
        return solve(0, cuts.size(), cuts, 0, n);
    }
};