1547. 切棍子的最小成本

题目链接

解题思路

• 这个题和戳气球有相同的思想，戳气球是以「最后戳哪个气球」组织答案，这个题是，「先切哪个」组织答案
• 戳气球

代码

class Solution {
public:

    // [L, R]上，怎么切？
    int process(vector<int> &cuts, int L, int R, vector<vector<int>> &dp) {
        if (L > R) {
            return 0;
        }
        if(L == R) {
            return cuts[R + 1] - cuts[L - 1];
        }
        if (dp[L][R] != -1) {
            return dp[L][R];
        }
        // 先切谁？
        int ans = INT32_MAX;
        for (int i = L; i <= R; ++i) {
            int next = process(cuts, L, i - 1, dp) + process(cuts, i + 1, R, dp) + cuts[R + 1] - cuts[L - 1];
            ans = min(ans, next);
        }
        dp[L][R] = ans;
        return ans;
    }

    int minCost(int n, vector<int>& cuts) {
        int m = cuts.size();
        sort(cuts.begin(), cuts.end());
        vector<int> newCuts(m + 2, 0);
        for (int i = 1; i <= m; ++i) {
            newCuts[i] = cuts[i - 1];
        }
        newCuts[m + 1] = n;
        vector<vector<int>> dp(m + 2, vector<int>(m + 2, -1));
        return process(newCuts, 1, m, dp);
    }
};