{"id":7242,"date":"2020-08-11T22:52:32","date_gmt":"2020-08-12T05:52:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7242"},"modified":"2020-08-11T23:07:34","modified_gmt":"2020-08-12T06:07:34","slug":"leetcode-1547-minimum-cost-to-cut-a-stick","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1547-minimum-cost-to-cut-a-stick\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1547. Minimum Cost to Cut a Stick"},"content":{"rendered":"\n<p>Given a wooden stick of length&nbsp;<code>n<\/code>&nbsp;units. The stick is labelled from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n<\/code>. For example, a stick of length&nbsp;<strong>6<\/strong>&nbsp;is labelled as follows:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/07\/21\/statement.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<p>Given an integer array&nbsp;<code>cuts<\/code>&nbsp;where&nbsp;<code>cuts[i]<\/code>&nbsp;denotes a position you should perform a cut at.<\/p>\n\n\n\n<p>You should perform the cuts in order, you can change the order of the cuts as you wish.<\/p>\n\n\n\n<p>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.<\/p>\n\n\n\n<p>Return&nbsp;<em>the minimum total cost<\/em>&nbsp;of the&nbsp;cuts.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/07\/23\/e1.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 7, cuts = [1,3,4,5]\n<strong>Output:<\/strong> 16\n<strong>Explanation:<\/strong> Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:\n\nThe 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.\nRearranging 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).<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 9, cuts = [5,6,1,4,2]\n<strong>Output:<\/strong> 22\n<strong>Explanation:<\/strong> If you try the given cuts ordering the cost will be 25.\nThere are much ordering with total cost &lt;= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= n &lt;= 10^6<\/code><\/li><li><code>1 &lt;= cuts.length &lt;= min(n - 1, 100)<\/code><\/li><li><code>1 &lt;= cuts[i] &lt;= n - 1<\/code><\/li><li>All the integers in&nbsp;<code>cuts<\/code>&nbsp;array are&nbsp;<strong>distinct<\/strong>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Range DP<\/strong><\/h2>\n\n\n\n<p>dp[i][j] := min cost to finish the i-th cuts to the j-th (in sorted order)<br>dp[i][j] = r &#8211; l + min(dp[i][k &#8211; 1], dp[k + 1][j]) # [l, r] is the current stick range.<\/p>\n\n\n\n<p>Time complexity: O(n^3)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int minCost(int n, vector<int>& cuts) {\n    const int kInf = 1e9;\n    sort(begin(cuts), end(cuts));\n    const int c = cuts.size();\n    vector<vector<int>> cost(c + 1, vector<int>(c + 1, kInf));\n    \/\/ Min cost to finish i-th cuts to the j-th cut with stick in range [l, r].\n    function<int(int, int, int, int)> dp = [&](int i, int j, int l, int r) {\n      if (i > j) return 0; \/\/ Done\n      if (i == j) return r - l; \/\/ One cut, the length of the stick.\n      if (cost[i][j] != kInf) return cost[i][j];\n      int& ans = cost[i][j];\n      for (int k = i; k <= j; ++k)\n        ans = min(ans, r - l \n                       + dp(i, k - 1, l, cuts[k]) \n                       + dp(k + 1, j, cuts[k], r));\n      return ans;\n    };\n    return dp(0, c - 1, 0, n);\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nclass Solution {  \n  public int minCost(int n, int[] cuts) {\n    Arrays.sort(cuts);\n    final int c = cuts.length;\n    int[][] dp = new int[c][c];\n    return solve(dp, cuts, 0, c - 1, 0, n);\n  }\n  \n  private int solve(int[][] dp, int[] cuts, int i, int j, int l, int r) {\n    if (i > j) return 0;\n    if (i == j) return r - l;\n    if (dp[i][j] != 0) return dp[i][j];\n    int ans = Integer.MAX_VALUE;\n    for (int k = i; k <= j; ++k)\n      ans = Math.min(ans, r - l \n                          + solve(dp, cuts, i, k - 1, l, cuts[k])\n                          + solve(dp, cuts, k + 1, j, cuts[k], r));\n    return dp[i][j] = ans;\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass Solution:\n  def minCost(self, n: int, cuts: List[int]) -> int:\n    @lru_cache(maxsize=None)\n    def dp(i, j, l, r):\n      if i > j: return 0\n      if i == j: return r - l\n      return r - l + min(dp(i, k - 1, l, cuts[k])\n                       + dp(k + 1, j, cuts[k], r) \n                         for k in range(i, j + 1))\n    cuts.sort()\n    return dp(0, len(cuts) - 1, 0, n)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a wooden stick of length&nbsp;n&nbsp;units. The stick is labelled from&nbsp;0&nbsp;to&nbsp;n. For example, a stick of length&nbsp;6&nbsp;is labelled as follows: Given an integer array&nbsp;cuts&nbsp;where&nbsp;cuts[i]&nbsp;denotes a&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[],"class_list":["post-7242","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7242","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7242"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7242\/revisions"}],"predecessor-version":[{"id":7245,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7242\/revisions\/7245"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7242"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7242"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7242"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}