{"id":4930,"date":"2019-03-02T21:46:35","date_gmt":"2019-03-03T05:46:35","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4930"},"modified":"2019-03-09T13:13:47","modified_gmt":"2019-03-09T21:13:47","slug":"leetcode-1000-minimum-cost-to-merge-stones","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1000-minimum-cost-to-merge-stones\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1000. Minimum Cost to Merge Stones"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1000. Minimum Cost to Merge Stones - \u5237\u9898\u627e\u5de5\u4f5c EP245\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/FabkoUzs64o?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>There are&nbsp;<code>N<\/code>&nbsp;piles of stones arranged in a row.&nbsp; The&nbsp;<code>i<\/code>-th pile has&nbsp;<code>stones[i]<\/code>&nbsp;stones.<\/p>\n\n\n\n<p>A&nbsp;<em>move<\/em>&nbsp;consists of merging&nbsp;<strong>exactly&nbsp;<code>K<\/code>&nbsp;consecutive<\/strong>&nbsp;piles into one pile, and the cost of this move is equal to the total number of stones in these&nbsp;<code>K<\/code>&nbsp;piles.<\/p>\n\n\n\n<p>Find the minimum cost to merge all piles of stones into one pile.&nbsp; If it is impossible, return&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>stones = [3,2,4,1], K = 2\n<strong>Output: <\/strong>20\n<strong>Explanation: <\/strong>\nWe start with [3, 2, 4, 1].\nWe merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].\nWe merge [4, 1] for a cost of 5, and we are left with [5, 5].\nWe merge [5, 5] for a cost of 10, and we are left with [10].\nThe total cost was 20, and this is the minimum possible.\n<\/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>stones = [3,2,4,1], K = 3\n<strong>Output: <\/strong>-1\n<strong>Explanation: <\/strong>After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>stones = [3,5,1,2,6], K = 3\n<strong>Output: <\/strong>25\n<strong>Explanation: <\/strong>\nWe start with [3, 5, 1, 2, 6].\nWe merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].\nWe merge [3, 8, 6] for a cost of 17, and we are left with [17].\nThe total cost was 25, and this is the minimum possible.\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= stones.length &lt;= 30<\/code><\/li><li><code>2 &lt;= K &lt;= 30<\/code><\/li><li><code>1 &lt;= stones[i] &lt;= 100<\/code><\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep245-1.png\" alt=\"\" class=\"wp-image-4947\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep245-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep245-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep245-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep2452.png\" alt=\"\" class=\"wp-image-4948\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep2452.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep2452-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep2452-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep245-3.png\" alt=\"\" class=\"wp-image-4949\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep245-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep245-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1000-ep245-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>dp[i][j][k] := min cost to merge subarray i ~ j into k piles<br>Init: dp[i][j][k] = 0 if i==j and k == 1 else inf<br>ans: dp[0][n-1][1]<br>transition: <br>1. dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]} for all  i &lt;= m &lt; j<br>2. dp[i][j][1] = dp[i][j][K] + sum(A[i]~A[j])<\/p>\n\n\n\n<p>Time complexity: O(n^3)<br>Space complexity: O(n^2*K)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Running time: 12 ms, 12.1 MB\nclass Solution {\npublic:\n  int mergeStones(vector<int>& stones, int K) {\n    const int n = stones.size();\n    if ((n - 1) % (K - 1)) return -1;\n    const int kInf = 1e9;    \n    vector<int> sums(n + 1);\n    for (int i = 0; i < stones.size(); ++i)\n      sums[i + 1] = sums[i] + stones[i];\n    \/\/ dp[i][j][k] := min cost to merge subarray i~j into k piles.\n    vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(K + 1, kInf)));\n    for (int i = 0; i < n; ++i)\n      dp[i][i][1] = 0;\n    \n    for (int l = 2; l <= n; ++l) \/\/ subproblem length\n      for (int i = 0; i <= n - l; ++i) { \/\/ start\n        int j = i + l - 1; \/\/ end\n        for (int k = 2; k <= K; ++k) \/\/ piles\n          for (int m = i; m < j; m += K - 1) \/\/ split point\n            dp[i][j][k] = min(dp[i][j][k], dp[i][m][1] + dp[m + 1][j][k - 1]);\n        dp[i][j][1] = dp[i][j][K] + sums[j + 1] - sums[i];\n      }        \n    return dp[0][n - 1][1];\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/top down<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 12 ms\nclass Solution {\npublic:\n  int mergeStones(vector<int>& stones, int K) {\n    const int n = stones.size();\n    if ((n - 1) % (K - 1)) return -1;\n    const int kInf = 1e9;\n    vector<int> sums(n + 1);\n    for (int i = 0; i < stones.size(); ++i)\n      sums[i + 1] = sums[i] + stones[i];\n    \n    vector<vector<vector<int>>> cache(n, vector<vector<int>>(n, vector<int>(K + 1, INT_MAX)));\n    std::function<int(int, int, int)> dp = [&stones, &sums, &cache, kInf, n, K, &dp](int i, int j, int k) {\n      if ((j - i + 1 - k) % (K - 1)) return kInf;\n      if (i == j) return k == 1 ? 0 : kInf;\n      if (cache[i][j][k] != INT_MAX) return cache[i][j][k];      \n      if (k == 1)\n        return cache[i][j][k] = dp(i, j, K) + sums[j + 1] - sums[i];\n      int ans = kInf;\n      for (int m = i; m < j; m += K - 1) {\n        int l = dp(i, m, 1);\n        if (l >= ans) continue;\n        int r = dp(m + 1, j, k - 1);\n        if (r >= ans) continue;\n        ans = min(ans, l + r);\n      }\n      return cache[i][j][k] = ans;\n    };\n    return dp(0, n - 1, 1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: DP<\/strong><\/h2>\n\n\n\n<p>dp[l][i] := min cost to merge [i, i + l) into as less piles as possible. Number of merges will be (l-1) \/ (K - 1) and <br>Transition: dp[l][i] = min(dp[m][i] + dp[l - m][i + m]) for 1 &lt;= m &lt; l<br>if ((l - 1) % (K - 1) == 0) [i, i + l) can be merged into 1 pile, dp[l][i] += sum(A[i:i+l])<\/p>\n\n\n\n<p>Time complexity: O(n^3 \/ k)<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++\">\n\/\/ Author: Huahua 4ms, 9.6 MB\nclass Solution {\npublic:\n  int mergeStones(vector<int>& stones, int K) {\n    const int n = stones.size();\n    if ((n - 1) % (K - 1)) return -1;\n        \n    vector<int> sums(n + 1);\n    for (int i = 0; i < stones.size(); ++i) \n      sums[i + 1] = sums[i] + stones[i];\n    \n    const int kInf = 1e9;\n    \/\/ dp[i][j] := min cost to merge subarray A[i] ~ A[j] into (j-i)%(K-1) + 1 piles\n    vector<vector<int>> dp(n, vector<int>(n, kInf));\n    for (int i = 0; i < n; ++i) dp[i][i] = 0;\n    \n    for (int l = 2; l <= n; ++l) \/\/ subproblem length \n      for (int i = 0; i <= n - l; ++i) { \/\/ start        \n        int j = i + l - 1;\n        for (int m = i; m < j ; m += K - 1) \/\/ split point\n            dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);\n        \/\/ If the current length can be merged into 1 pile\n        \/\/ The cost is independent of the merge orders.\n        if ((l - 1) % (K - 1) == 0)\n          dp[i][j] += sums[j + 1] - sums[i];\n      }\n    return dp[0][n - 1];\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/Top-Down<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, 4 ms\nclass Solution {\npublic:\n  int mergeStones(vector<int>& stones, int K) {\n    const int n = stones.size();\n    if ((n - 1) % (K - 1)) return -1;\n    const int kInf = 1e9;\n    vector<vector<int>> cache(n, vector<int>(n, kInf));    \n    vector<int> sums(n + 1);\n    for (int i = 0; i < stones.size(); ++i) sums[i + 1] = sums[i] + stones[i];\n    \n    std::function<int(int, int)> dp;\n    dp = [&stones, &sums, &cache, &dp, K, kInf](int i, int j) {\n      const int l = j - i + 1;\n      if (l < K) return 0;\n      if (cache[i][j] != kInf) return cache[i][j];\n      int ans = kInf;\n      for (int m = i; m < j ; m += K - 1) \/\/ split point\n        ans = min(ans, dp(i, m) + dp(m + 1, j));\n      if ((l - 1) % (K - 1) == 0)\n        ans += sums[j + 1] - sums[i];\n      return cache[i][j] = ans;\n    };    \n    return dp(0, n - 1);  \n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are&nbsp;N&nbsp;piles of stones arranged in a row.&nbsp; The&nbsp;i-th pile has&nbsp;stones[i]&nbsp;stones. A&nbsp;move&nbsp;consists of merging&nbsp;exactly&nbsp;K&nbsp;consecutive&nbsp;piles into one pile, and the cost of this move is equal&#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":[18,26,217],"class_list":["post-4930","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-dynamic-programming","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4930","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=4930"}],"version-history":[{"count":18,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4930\/revisions"}],"predecessor-version":[{"id":4955,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4930\/revisions\/4955"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4930"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4930"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4930"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}