{"id":8478,"date":"2021-08-04T23:26:50","date_gmt":"2021-08-05T06:26:50","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8478"},"modified":"2021-08-04T23:27:19","modified_gmt":"2021-08-05T06:27:19","slug":"leetcode-1866-number-of-ways-to-rearrange-sticks-with-k-sticks-visible","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1866-number-of-ways-to-rearrange-sticks-with-k-sticks-visible\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible"},"content":{"rendered":"\n<p>There are&nbsp;<code>n<\/code>&nbsp;uniquely-sized sticks whose lengths are integers from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>. You want to arrange the sticks such that&nbsp;<strong>exactly<\/strong>&nbsp;<code>k<\/code>&nbsp;sticks are&nbsp;<strong>visible<\/strong>&nbsp;from the left. A stick&nbsp;is&nbsp;<strong>visible<\/strong>&nbsp;from the left if there are no&nbsp;<strong>longer<\/strong>&nbsp;sticks to the&nbsp;<strong>left<\/strong>&nbsp;of it.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if the sticks are arranged&nbsp;<code>[<u>1<\/u>,<u>3<\/u>,2,<u>5<\/u>,4]<\/code>, then the sticks with lengths&nbsp;<code>1<\/code>,&nbsp;<code>3<\/code>, and&nbsp;<code>5<\/code>&nbsp;are visible from the left.<\/li><\/ul>\n\n\n\n<p>Given&nbsp;<code>n<\/code>&nbsp;and&nbsp;<code>k<\/code>, return&nbsp;<em>the&nbsp;<strong>number<\/strong>&nbsp;of such arrangements<\/em>. Since the answer may be large, 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<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3, k = 2\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.\nThe visible sticks are underlined.\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> n = 5, k = 5\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.\nThe visible sticks are underlined.\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 = 20, k = 11\n<strong>Output:<\/strong> 647427950\n<strong>Explanation:<\/strong> There are 647427950 (mod 10<sup>9 <\/sup>+ 7) ways to rearrange the sticks such that exactly 11 sticks are visible.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 1000<\/code><\/li><li><code>1 &lt;= k &lt;= n<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>dp(n, k) = dp(n &#8211; 1, k &#8211; 1) + (n-1) * dp(n-1, k)<\/p>\n\n\n\n<p>Time complexity: O(n*k)<br>Space complexity: O(n*k) -&gt; O(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\/\/ Author: Huahua\nclass Solution {\npublic:\n  int rearrangeSticks(int n, int k) {\n    constexpr int kMod = 1e9 + 7;\n    vector<vector<long>> dp(n + 1, vector<long>(k + 1));        \n    for (int j = 1; j <= k; ++j) {\n      dp[j][j] = 1;\n      for (int i = j + 1; i <= n; ++i)\n        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % kMod;\n    }\n    return dp[n][k];\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  @lru_cache(maxsize=None)\n  def rearrangeSticks(self, n: int, k: int) -> int:\n    if k == 0: return 0\n    if k == n or n <= 2: return 1\n    return (self.rearrangeSticks(n - 1, k - 1) + \n            (n - 1) * self.rearrangeSticks(n - 1, k)) % (10**9 + 7)\n        \n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are&nbsp;n&nbsp;uniquely-sized sticks whose lengths are integers from&nbsp;1&nbsp;to&nbsp;n. You want to arrange the sticks such that&nbsp;exactly&nbsp;k&nbsp;sticks are&nbsp;visible&nbsp;from the left. A stick&nbsp;is&nbsp;visible&nbsp;from the left if there&#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,8,18,217],"class_list":["post-8478","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-combination","tag-counting","tag-dp","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8478","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=8478"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8478\/revisions"}],"predecessor-version":[{"id":8480,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8478\/revisions\/8480"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8478"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8478"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8478"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}