{"id":6889,"date":"2020-06-07T00:53:52","date_gmt":"2020-06-07T07:53:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6889"},"modified":"2020-06-07T10:06:28","modified_gmt":"2020-06-07T17:06:28","slug":"leetcode-1473-paint-house-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1473-paint-house-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1473. Paint House III"},"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 1473. Paint House III - \u5237\u9898\u627e\u5de5\u4f5c EP333\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/53b32Upplk0?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 is&nbsp;a row of&nbsp;<code>m<\/code>&nbsp;houses in a small city, each house must be painted with one of the&nbsp;<code>n<\/code>&nbsp;colors (labeled from 1 to&nbsp;<code>n<\/code>), some houses that has been painted last summer should not be painted again.<\/p>\n\n\n\n<p>A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods&nbsp; [{1}, {2,2}, {3,3}, {2}, {1,1}]).<\/p>\n\n\n\n<p>Given an array&nbsp;<code>houses<\/code>, an&nbsp;<code>m * n<\/code>&nbsp;matrix&nbsp;<code>cost<\/code>&nbsp;and&nbsp;an integer&nbsp;<code>target<\/code>&nbsp;where:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>houses[i]<\/code>:&nbsp;is the color of the house&nbsp;<code>i<\/code>,&nbsp;<strong>0<\/strong>&nbsp;if the house is not painted yet.<\/li><li><code>cost[i][j]<\/code>: is the cost of paint the house&nbsp;<code>i<\/code>&nbsp;with the color&nbsp;<code>j+1<\/code>.<\/li><\/ul>\n\n\n\n<p>Return the minimum cost of painting all the&nbsp;remaining houses in such a way that there are exactly&nbsp;<code>target<\/code>&nbsp;neighborhoods, if&nbsp;not possible return&nbsp;<strong>-1<\/strong>.<\/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> houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3\n<strong>Output:<\/strong> 9\n<strong>Explanation:<\/strong> Paint houses of this way [1,2,2,1,1]\nThis array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].\nCost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.\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> houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3\n<strong>Output:<\/strong> 11\n<strong>Explanation:<\/strong> Some houses are already painted, Paint the houses of this way [2,2,1,2,2]\nThis array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. \nCost of paint the first and last house (10 + 1) = 11.\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> houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5\n<strong>Output:<\/strong> 5\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> houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == houses.length == cost.length<\/code><\/li><li><code>n == cost[i].length<\/code><\/li><li><code>1 &lt;= m &lt;= 100<\/code><\/li><li><code>1 &lt;= n &lt;= 20<\/code><\/li><li><code>1 &lt;= target&nbsp;&lt;= m<\/code><\/li><li><code>0 &lt;= houses[i]&nbsp;&lt;= n<\/code><\/li><li><code>1 &lt;= cost[i][j] &lt;= 10^4<\/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\/06\/1473-ep333.png\" alt=\"\" class=\"wp-image-6894\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1473-ep333.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1473-ep333-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/06\/1473-ep333-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[k][i][c] := min cost to form k neighbors with first i houses and i-th house is in color c.<\/p>\n\n\n\n<p>dp[k][i][c] := min{dp[k-(c != cj)][j][cj] for cj in 1..n} +  0 if houses[i] == c else cost[i][c]<\/p>\n\n\n\n<p>init: dp[0][0][*] = 0 otherwise inf<br>ans = min(dp[target][m])<\/p>\n\n\n\n<p>Time complexity: O(T*M*N^2)<br>Space complexity: O(T*M*N) -&gt; O(M*N)<\/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\n\/\/ Author: Huahua\uff0c 104ms, 17.9MB\nclass Solution {\npublic:\n  int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {\n    constexpr int kInf = 1e9 + 7, s = 1;    \n    \/\/ dp[k][i][c] := min cost to form k neighbors with first i houses and end with color c. \n    vector<vector<vector<int>>> dp(target + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, kInf)));\n    fill(begin(dp[0][0]), end(dp[0][0]), 0);\n    for (int k = 1; k <= target; ++k)\n      for (int i = k; i <= m; ++i) {\n        const int hi = houses[i - 1];\n        const int hj = i >= 2 ? houses[i - 2] : 0;\n        const auto& [si, ei] = hi ? tie(hi, hi) : tie(s, n);\n        const auto& [sj, ej] = hj ? tie(hj, hj) : tie(s, n);\n        for (int ci = si; ci <= ei; ++ci) {\n          const int v = ci == hi ? 0 : cost[i - 1][ci - 1];\n          for (int cj = sj; cj <= ej; ++cj)\n            dp[k][i][ci] = min(dp[k][i][ci], dp[k - (ci != cj)][i - 1][cj] + v);\n        }\n      }\n    const int ans = *min_element(begin(dp[target][m]), end(dp[target][m]));\n    return ans >= kInf ? -1 : ans;\n  }\n};\n\n\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>There is&nbsp;a row of&nbsp;m&nbsp;houses in a small city, each house must be painted with one of the&nbsp;n&nbsp;colors (labeled from 1 to&nbsp;n), some houses that has&#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,217],"class_list":["post-6889","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6889","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=6889"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6889\/revisions"}],"predecessor-version":[{"id":6895,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6889\/revisions\/6895"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6889"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6889"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6889"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}