{"id":6788,"date":"2020-05-18T09:24:47","date_gmt":"2020-05-18T16:24:47","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6788"},"modified":"2020-05-19T09:48:32","modified_gmt":"2020-05-19T16:48:32","slug":"leetcode-1449-form-largest-integer-with-digits-that-add-up-to-target","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1449-form-largest-integer-with-digits-that-add-up-to-target\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1449. Form Largest Integer With Digits That Add up to Target"},"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 1449. Form Largest Integer With Digits That Add up to Target - \u5237\u9898\u627e\u5de5\u4f5c EP327\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/J43N1o1XhqE?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>Given an array of integers&nbsp;<code>cost<\/code>&nbsp;and an integer&nbsp;<code>target<\/code>. Return the&nbsp;<strong>maximum<\/strong>&nbsp;integer you can paint&nbsp;under the following rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The cost of painting a&nbsp;digit (i+1) is given by&nbsp;<code>cost[i]<\/code>&nbsp;(0 indexed).<\/li><li>The total cost used must&nbsp;be equal to&nbsp;<code>target<\/code>.<\/li><li>Integer does not have digits 0.<\/li><\/ul>\n\n\n\n<p>Since the answer may be too large, return it as string.<\/p>\n\n\n\n<p>If there is no way to paint any integer given the condition, return &#8220;0&#8221;.<\/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> cost = [4,3,2,5,6,7,2,5,5], target = 9\n<strong>Output:<\/strong> \"7772\"\n<strong>Explanation: <\/strong> The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost(\"7772\") = 2*3+ 3*1 = 9. You could also paint \"997\", but \"7772\" is the largest number.\n<strong>Digit    cost<\/strong>\n  1  -&gt;   4\n  2  -&gt;   3\n  3  -&gt;   2\n  4  -&gt;   5\n  5  -&gt;   6\n  6  -&gt;   7\n  7  -&gt;   2\n  8  -&gt;   5\n  9  -&gt;   5\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> cost = [7,6,5,5,5,6,8,7,8], target = 12\n<strong>Output:<\/strong> \"85\"\n<strong>Explanation:<\/strong> The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost(\"85\") = 7 + 5 = 12.\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> cost = [2,4,6,2,4,6,4,4,4], target = 5\n<strong>Output:<\/strong> \"0\"\n<strong>Explanation:<\/strong> It's not possible to paint any integer with total cost equal to target.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> cost = [6,10,15,40,40,40,40,40,40], target = 47\n<strong>Output:<\/strong> \"32211\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>cost.length == 9<\/code><\/li><li><code>1 &lt;= cost[i] &lt;= 5000<\/code><\/li><li><code>1 &lt;= target &lt;= 5000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1449-ep327-1.png\" alt=\"\" class=\"wp-image-6798\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1449-ep327-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1449-ep327-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1449-ep327-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp(target) := largest number to print with cost == target.<br>dp(target) = max(dp(target &#8211; d) + cost[d])<\/p>\n\n\n\n<p>Time complexity: O(target^2)<br>Space complexity: O(target^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ \/ Top Down<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 280 ms\nclass Solution {\npublic:\n  string largestNumber(vector<int>& cost, int target) {    \n    vector<string> cache(target + 1);\n    \/\/ dp[i] := largestNumber that has cost i.\n    function<string(int)> dp = [&](int t) -> string {\n      if (t < 0) return \"0\"; \/\/ Invalid.\n      if (t == 0) return \"\"; \/\/ Found a solution.\n      if (!cache[t].empty()) return cache[t];\n      cache[t] = \"0\"; \/\/ Important !!!\n      for (int d = 1; d <= 9; ++d) {\n        const string&#038; cur = dp(t - cost[d - 1]);        \n        if (cur != \"0\" &#038;&#038; cur.length() + 1 >= cache[t].length())\n          cache[t] = to_string(d) + cur;\n      }\n      return cache[t];\n    };\n    return dp(target);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ \/ Bottom Up<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 240 ms\nclass Solution {\npublic:\n  string largestNumber(vector<int>& cost, int target) {    \n    \/\/ dp[i] := largestNumber that has cost i.\n    vector<string> dp(target + 1, \"0\");\n    dp[0] = \"\";\n    for (int t = 1; t <= target; ++t)\n      for (int d = 1; d <= 9; ++d) {\n        const int s = t - cost[d - 1];\n        if (s < 0 || dp[s] == \"0\" \n            || dp[s].length() + 1 < dp[t].length()) continue;\n        dp[t] = to_string(d) + dp[s];\n      }\n    return dp[target];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>To avoid string copying, we can store digit added (in order to back track the parent) and length of the optimal string.<\/p>\n\n\n\n<p>Time complexity: O(target)<br>Space complexity: O(target)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ \/ O(target)<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 25 ms\nclass Solution {\npublic:\n  string largestNumber(vector<int>& cost, int target) {\n    vector<pair<int, int>> cache(target + 1, {-1, -1});\n    \/\/ dp[i] := {digit, length} of largestNumber that has cost i.\n    function<pair<int, int>(int)> dp = [&](int t) -> pair<int, int> {\n      if (t < 0) return {0, -1}; \/\/ Invalid.\n      if (t == 0) return {0, 0}; \/\/ Found a solution.\n      if (cache[t].first != -1) return cache[t];\n      cache[t] = {0, -1}; \/\/ make as solved but invalid.\n      for (int d = 1; d <= 9; ++d) {\n        const int l = dp(t - cost[d - 1]).second;\n        if (l != -1 &#038;&#038; l + 1 >= cache[t].second)\n          cache[t] = {d, l + 1};\n      }\n      return cache[t];\n    };\n    dp(target);\n    if (cache[target].second <= 0) return \"0\";\n    string ans;\n    while (target) {\n      ans += cache[target].first + '0';\n      target -= cost[cache[target].first - 1];\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ \/ O(target)<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 28 ms\nclass Solution {\npublic:\n  string largestNumber(vector<int>& cost, int target) {    \n    \/\/ dp[i] = {d, length} of the largest number that costs i.\n    vector<pair<int, int>> dp(target + 1, {-1, -1});\n    dp[0] = {0, 0};\n    for (int t = 1; t <= target; ++t)\n      for (int d = 1; d <= 9; ++d) {\n        const int s = t - cost[d - 1];\n        if (s < 0 || dp[s].second == -1\n            || dp[s].second + 1 < dp[t].second) continue;\n        dp[t] = {d, dp[s].second + 1};\n      }\n    if (dp[target].second == -1) return \"0\";\n    string ans;\n    while (target) {\n      ans += dp[target].first + '0';\n      target -= cost[dp[target].first - 1];\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given an array of integers&nbsp;cost&nbsp;and an integer&nbsp;target. Return the&nbsp;maximum&nbsp;integer you can paint&nbsp;under the following rules: The cost of painting a&nbsp;digit (i+1) is given by&nbsp;cost[i]&nbsp;(0 indexed).&#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":[4],"class_list":["post-6788","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6788","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=6788"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6788\/revisions"}],"predecessor-version":[{"id":6800,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6788\/revisions\/6800"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6788"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6788"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6788"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}