{"id":5313,"date":"2019-07-20T21:47:20","date_gmt":"2019-07-21T04:47:20","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5313"},"modified":"2019-07-21T09:27:50","modified_gmt":"2019-07-21T16:27:50","slug":"1130-minimum-cost-tree-from-leaf-values","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/1130-minimum-cost-tree-from-leaf-values\/","title":{"rendered":"\u82b1\u82b1\u9171 1130. Minimum Cost Tree From Leaf Values"},"content":{"rendered":"\n<p>Given an array&nbsp;<code>arr<\/code>&nbsp;of positive integers, consider all binary trees such that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Each node has either 0 or 2 children;<\/li><li>The values of&nbsp;<code>arr<\/code>&nbsp;correspond to the values of each&nbsp;<strong>leaf<\/strong>&nbsp;in an in-order traversal of the tree.&nbsp;&nbsp;<em>(Recall that a node is a leaf if and only if it has 0 children.)<\/em><\/li><li>The value&nbsp;of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.<\/li><\/ul>\n\n\n\n<p>Among all possible binary trees considered,&nbsp;return the smallest possible sum of the values of each non-leaf node.&nbsp; It is guaranteed this sum fits into a 32-bit integer.<\/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> arr = [6,2,4]\n<strong>Output:<\/strong> 32\n<strong>Explanation:<\/strong>\nThere are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.\n\n    24            24\n   \/  \\          \/  \\\n  12   4        6    8\n \/  \\               \/ \\\n6    2             2   4\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= arr.length &lt;= 40<\/code><\/li><li><code>1 &lt;= arr[i] &lt;= 15<\/code><\/li><li>It is guaranteed that the answer fits into a 32-bit signed integer (ie.&nbsp;it is less than&nbsp;<code>2^31<\/code>).<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>dp[i][j] := answer of build a tree from a[i] ~ a[j]<br>dp[i][j] = min{dp[i][k] + dp[k+1][j] + max(a[i~k]) * max(a[k+1~j])} i &lt;= k &lt; j<\/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 mctFromLeafValues(vector<int>& arr) {\n    const int n = arr.size();\n    vector<vector<int>> dp(n, vector<int>(n));\n    vector<vector<int>> m(n, vector<int>(n));    \n    for (int i = 0; i < n; ++i) {\n      m[i][i] = arr[i];\n      for (int j = i + 1; j < n; ++j)\n        m[i][j] = max(m[i][j - 1], arr[j]);\n    }    \n    for (int l = 2; l <= n; ++l)\n      for (int i = 0; i + l <= n; ++i) {        \n        int j = i + l - 1; \n        dp[i][j] = INT_MAX;\n        for (int k = i; k < j; ++k)                \n          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + m[i][k] * m[k+1][j]);\n      }\n    return dp[0][n - 1];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array&nbsp;arr&nbsp;of positive integers, consider all binary trees such that: Each node has either 0 or 2 children; The values of&nbsp;arr&nbsp;correspond to the values&#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,177],"class_list":["post-5313","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5313","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=5313"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5313\/revisions"}],"predecessor-version":[{"id":5323,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5313\/revisions\/5323"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5313"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}