There are n
uniquely-sized sticks whose lengths are integers from 1
to n
. You want to arrange the sticks such that exactly k
sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.
- For example, if the sticks are arranged
[1,3,2,5,4]
, then the sticks with lengths1
,3
, and5
are visible from the left.
Given n
and k
, return the number of such arrangements. Since the answer may be large, return it modulo 109 + 7
.
Example 1:
Input: n = 3, k = 2 Output: 3 Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible. The visible sticks are underlined.
Example 2:
Input: n = 5, k = 5 Output: 1 Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible. The visible sticks are underlined.
Example 3:
Input: n = 20, k = 11 Output: 647427950 Explanation: There are 647427950 (mod 109 + 7) ways to rearrange the sticks such that exactly 11 sticks are visible.
Constraints:
1 <= n <= 1000
1 <= k <= n
Solution: DP
dp(n, k) = dp(n – 1, k – 1) + (n-1) * dp(n-1, k)
Time complexity: O(n*k)
Space complexity: O(n*k) -> O(k)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int rearrangeSticks(int n, int k) { constexpr int kMod = 1e9 + 7; vector<vector<long>> dp(n + 1, vector<long>(k + 1)); for (int j = 1; j <= k; ++j) { dp[j][j] = 1; for (int i = j + 1; i <= n; ++i) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % kMod; } return dp[n][k]; } }; |
Python3
1 2 3 4 5 6 7 8 |
# Author: Huahua class Solution: @lru_cache(maxsize=None) def rearrangeSticks(self, n: int, k: int) -> int: if k == 0: return 0 if k == n or n <= 2: return 1 return (self.rearrangeSticks(n - 1, k - 1) + (n - 1) * self.rearrangeSticks(n - 1, k)) % (10**9 + 7) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment