you try the given cuts ordering the cost will be 25. There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints

2 <= n <= 106
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
All the integers in cuts array are distinct.

Solution

Method 1 – Dynamic Programming (Interval DP)

Intuition

Use dynamic programming to find the minimum cost to cut each interval, by trying all possible first cuts and combining the results.

Approach

Add 0 and n to the cuts array and sort it.
Let dp[i][j] be the minimum cost to cut the stick between cuts[i] and cuts[j].
For each interval, try all possible first cuts and recursively compute the cost for left and right segments.
The answer is dp[0][m-1], where m is the number of cuts (including 0 and n).

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minCost(int n, vector<int>& cuts) {\n        cuts.push_back(0);\n        cuts.push_back(n);\n        sort(cuts.begin(), cuts.end());\n        int m = cuts.size();\n        vector<vector<int>> dp(m, vector<int>(m));\n        for (int l = 2; l < m; ++l) {\n            for (int i = 0; i + l < m; ++i) {

Related Tags