{"id":7519,"date":"2020-10-17T14:50:56","date_gmt":"2020-10-17T21:50:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7519"},"modified":"2020-10-21T00:38:19","modified_gmt":"2020-10-21T07:38:19","slug":"leetcode-1621-number-of-sets-of-k-non-overlapping-line-segments","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1621-number-of-sets-of-k-non-overlapping-line-segments\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1621. Number of Sets of K Non-Overlapping Line Segments"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1621. Number of Sets of K Non-Overlapping Line Segments - \u5237\u9898\u627e\u5de5\u4f5c EP363\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/AJoe3EXyYLc?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&nbsp;<code>n<\/code>&nbsp;points on a 1-D plane, where the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;point (from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n-1<\/code>) is at&nbsp;<code>x = i<\/code>, find the number of ways we can draw&nbsp;<strong>exactly<\/strong>&nbsp;<code>k<\/code>&nbsp;<strong>non-overlapping<\/strong>&nbsp;line segments such that each segment covers two or more points. The endpoints of each segment must have&nbsp;<strong>integral coordinates<\/strong>. The&nbsp;<code>k<\/code>&nbsp;line segments&nbsp;<strong>do not<\/strong>&nbsp;have to cover all&nbsp;<code>n<\/code>&nbsp;points, and they are&nbsp;<strong>allowed<\/strong>&nbsp;to share endpoints.<\/p>\n\n\n\n<p>Return&nbsp;<em>the number of ways we can draw&nbsp;<\/em><code>k<\/code><em>&nbsp;non-overlapping line segments<\/em><em>.<\/em>&nbsp;Since this number can be huge, return it&nbsp;<strong>modulo<\/strong>&nbsp;<code>10<sup>9<\/sup>&nbsp;+ 7<\/code>.<\/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\/09\/07\/ex1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 4, k = 2\n<strong>Output:<\/strong> 5\n<strong>Explanation: \n<\/strong>The two line segments are shown in red and blue.\nThe image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.<\/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 = 3, k = 1\n<strong>Output:<\/strong> 3\n<strong>Explanation: <\/strong>The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.\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> n = 30, k = 7\n<strong>Output:<\/strong> 796297179\n<strong>Explanation: <\/strong>The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10<sup>9<\/sup> + 7 gives us 796297179.\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> n = 5, k = 3\n<strong>Output:<\/strong> 7\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3, k = 2\n<strong>Output:<\/strong> 1<\/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;= 1000<\/code><\/li><li><code>1 &lt;= k &lt;= n-1<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Naive DP (TLE)<\/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\/10\/1621-ep363-1.png\" alt=\"\" class=\"wp-image-7541\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[n][k] := ans of problem(n, k)<br>dp[n][1] = n * (n &#8211; 1) \/ 2   # C(n,2)<br>dp[n][k] = 1 if k == n &#8211; 1<br>dp[n][k] = 0 if k &gt;= n<br>dp[n][k] = sum((i &#8211; 1) * dp(n &#8211; i + 1, k &#8211; 1) 2 &lt;= i &lt; n<\/p>\n\n\n\n<p>Time complexity: O(n^2*k)<br>Space complexity: O(n*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++\">\nclass Solution {\npublic:\n  int numberOfSets(int n, int k) {\n    constexpr int kMod = 1e9 + 7;\n    vector<vector<int>> cache(n + 1, vector<int>(k + 1));\n    function<int(int, int)> dp = [&](int n, int k) {\n      if (k >= n) return 0;\n      if (k == 1) return n * (n - 1) \/ 2;\n      if (k == n - 1) return 1;      \n      int& ans = cache[n][k];\n      if (ans) return ans;\n      for (long i = 2; i < n; ++i) {\n        const int t = ((i - 1) * dp(n - i + 1, k - 1)) % kMod;\n        ans = (ans + t) % kMod;\n      }     \n      return ans;\n    };\n    return dp(n, k);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: DP w\/ Prefix Sum<\/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\/10\/1621-ep363-2.png\" alt=\"\" class=\"wp-image-7540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(nk)<br>Space complexity: O(nk)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua 940 ms\nclass Solution:\n  def numberOfSets(self, n: int, k: int) -> int:\n    kMod = 10**9 + 7\n    dp = [[0] * (k + 1) for _ in range(n + 1)]\n    \n    for i in range(n + 1):\n      dp[i][0] = 1\n      \n    for j in range(1, k + 1):\n      s = 0\n      for i in range(1, n + 1):        \n        dp[i][j] = (s + dp[i - 1][j])\n        s += dp[i][j - 1]\n    return dp[n][k] % kMod\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 3: DP \/ 3D State<\/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\/10\/1621-ep363-3.png\" alt=\"\" class=\"wp-image-7542\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(nk)<br>Space complexity: O(nk)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua 940 ms\nclass Solution:\n  def numberOfSets(self, n: int, k: int) -> int:    \n    kMod = 10**9 + 7\n    \n    @lru_cache(None)\n    def dp(n: int, k: int, e: int) -> int: \n      if k == 0: return 1\n      if k > n: return 0\n      return (dp(n - 1, k, e) + dp(n + e - 1, k - e, 1 - e)) % kMod\n    return dp(n, k, 0)\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 4: DP \/ Mathematical induction<\/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\/10\/1621-ep363-4.png\" alt=\"\" class=\"wp-image-7543\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\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\/10\/1621-ep363-5.png\" alt=\"\" class=\"wp-image-7544\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-5.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-5-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-5-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(nk)<br>Space complexity: O(nk)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua 648 ms\nclass Solution:\n  def numberOfSets(self, n: int, k: int) -> int:        \n    @lru_cache(None)\n    def dp(n: int, k: int) -> int: \n      if k >= n: return 0\n      if k == 1: return n * (n - 1) \/\/ 2\n      if k == n - 1: return 1\n      return 2 * dp(n - 1, k) - dp(n - 2, k) + dp(n - 1, k - 1)\n    \n    return dp(n, k) % (10**9 + 7)\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 5: DP \/ Reduction<\/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\/10\/1621-ep363-6.png\" alt=\"\" class=\"wp-image-7545\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-6.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-6-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1621-ep363-6-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>This problem can be reduced to: given n + k - 1 points, pick k segments (2*k points). <br>if two consecutive points were selected by two segments e.g. i for A and i+1 for B, then they share a point in the original space. <br>Answer C(n + k - 1, 2*k)<\/p>\n\n\n\n<p>Time complexity: O((n+k)*2) Pascal's triangle<br>Space complexity: O((n+k)*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 numberOfSets(int n, int k) {\n    constexpr int kMod = 1e9 + 7;\n    vector<vector<int>> dp(n + k , vector<int>(n + k));\n    for (int i = 0; i < n + k; ++i) {\n      dp[i][0] = dp[i][i] = 1;\n      for (int j = 1; j < i; ++j)\n        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % kMod;\n    }\n    return dp[n + k - 1][2 * k];\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given&nbsp;n&nbsp;points on a 1-D plane, where the&nbsp;ith&nbsp;point (from&nbsp;0&nbsp;to&nbsp;n-1) is at&nbsp;x = i, find the number of ways we can draw&nbsp;exactly&nbsp;k&nbsp;non-overlapping&nbsp;line segments such that each segment&#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":[122,18,177],"class_list":["post-7519","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-combination","tag-dp","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7519","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=7519"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7519\/revisions"}],"predecessor-version":[{"id":7548,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7519\/revisions\/7548"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7519"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7519"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7519"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}