5486. 切棍子的最小成本

有一根長(zhǎng)度為 n 個(gè)單位的木棍，棍上從 0 到 n 標(biāo)記了若干位置。例如，長(zhǎng)度為 6 的棍子可以標(biāo)記如下：
給你一個(gè)整數(shù)數(shù)組 cuts ，其中 cuts[i] 表示你需要將棍子切開的位置。
你可以按順序完成切割，也可以根據(jù)需要更改切割的順序。

每次切割的成本都是當(dāng)前要切割的棍子的長(zhǎng)度，切棍子的總成本是歷次切割成本的總和。對(duì)棍子進(jìn)行切割將會(huì)把一根木棍分成兩根較小的木棍（這兩根木棍的長(zhǎng)度和就是切割前木棍的長(zhǎng)度）。請(qǐng)參閱第一個(gè)示例以獲得更直觀的解釋。

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

解題思路：

這題看起來是找最佳切割順序，有一定誤導(dǎo)性；其實(shí)這道題和高樓扔雞蛋很相似。
根據(jù)因?yàn)樽疃嘀恍枰?100次，所有我們可以采用分治的思想。將復(fù)雜問題轉(zhuǎn)化為一個(gè)個(gè)的子問題，遞歸求解。
因?yàn)榭偟们幸坏叮谝淮蜗入S意選一個(gè)切割點(diǎn)。然后找出第一刀所有可行解的最優(yōu)解。

遞推公式：

dp[i][j] 表示 cuts[i] ~ cutsj,這些切割點(diǎn)，所有切割順序的最優(yōu)解。
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) } + 當(dāng)前這一刀的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]),這些切割點(diǎn)的最優(yōu)解
    // 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)} + 當(dāng)前這一刀的cost
    int solve(int i, int j, vector<int>& cuts, int wooden_start, int wooden_end){
        if (i >= j) {
            return 0;
        }
        // 直接返回結(jié)果
        if(dp[i][j] >= 0) {
            return dp[i][j];
        }
        // 首次隨意選一個(gè)點(diǎn),切下去
        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);
    }
};