Given a wooden stick of length n
units. The stick is labelled from 0
to n
. For example, a stick of length 6 is labelled as follows:
Given an integer array cuts
where cuts[i]
denotes a position you should perform a cut at.
You should perform the cuts in order, you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.
Return the minimum total cost of the cuts.
Example 1:
Input: n = 7, cuts = [1,3,4,5] Output: 16 Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario: The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20. Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).
Example 2:
Input: n = 9, cuts = [5,6,1,4,2] Output: 22 Explanation: If 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 <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
- All the integers in
cuts
array are distinct.
Solution: Range DP
dp[i][j] := min cost to finish the i-th cuts to the j-th (in sorted order)
dp[i][j] = r – l + min(dp[i][k – 1], dp[k + 1][j]) # [l, r] is the current stick range.
Time complexity: O(n^3)
Space complexity: O(n^2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: int minCost(int n, vector<int>& cuts) { const int kInf = 1e9; sort(begin(cuts), end(cuts)); const int c = cuts.size(); vector<vector<int>> cost(c + 1, vector<int>(c + 1, kInf)); // Min cost to finish i-th cuts to the j-th cut with stick in range [l, r]. function<int(int, int, int, int)> dp = [&](int i, int j, int l, int r) { if (i > j) return 0; // Done if (i == j) return r - l; // One cut, the length of the stick. if (cost[i][j] != kInf) return cost[i][j]; int& ans = cost[i][j]; for (int k = i; k <= j; ++k) ans = min(ans, r - l + dp(i, k - 1, l, cuts[k]) + dp(k + 1, j, cuts[k], r)); return ans; }; return dp(0, c - 1, 0, n); } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public int minCost(int n, int[] cuts) { Arrays.sort(cuts); final int c = cuts.length; int[][] dp = new int[c][c]; return solve(dp, cuts, 0, c - 1, 0, n); } private int solve(int[][] dp, int[] cuts, int i, int j, int l, int r) { if (i > j) return 0; if (i == j) return r - l; if (dp[i][j] != 0) return dp[i][j]; int ans = Integer.MAX_VALUE; for (int k = i; k <= j; ++k) ans = Math.min(ans, r - l + solve(dp, cuts, i, k - 1, l, cuts[k]) + solve(dp, cuts, k + 1, j, cuts[k], r)); return dp[i][j] = ans; } } |
Python3
1 2 3 4 5 6 7 8 9 10 11 |
class Solution: def minCost(self, n: int, cuts: List[int]) -> int: @lru_cache(maxsize=None) def dp(i, j, l, r): if i > j: return 0 if i == j: return r - l return r - l + min(dp(i, k - 1, l, cuts[k]) + dp(k + 1, j, cuts[k], r) for k in range(i, j + 1)) cuts.sort() return dp(0, len(cuts) - 1, 0, n) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment