Formatted question description: https://leetcode.ca/all/1866.html
1866. Number of Ways to Rearrange Sticks With K Sticks Visible
Level
Hard
Description
There are n
uniquelysized 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 10^9 + 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
Use dynamic programming. Create a 2D array dp
with n + 1
rows and n + 1
columns, where dp[i][j]
represents the number of ways to rearrange i
sticks with j
sticks visible, where i >= j >= 1
.
The base case of dp
is that dp[i][i] = 1
for all 1 <= i <= n
. For the rest values, dp[i][j] = dp[i  1][j  1] + dp[i  1][j] * (i  1)
.
Finally, return dp[n][k]
.

class Solution { public int rearrangeSticks(int n, int k) { final int MODULO = 1000000007; int[][] dp = new int[n + 1][n + 1]; for (int i = 1; i <= n; i++) dp[i][i] = 1; for (int i = 2; i <= n; i++) { dp[i][1] = (int) ((long) dp[i  1][1] * (i  1) % MODULO); for (int j = 2; j <= i; j++) dp[i][j] = (int) ((dp[i  1][j  1] + (long) dp[i  1][j] * (i  1)) % MODULO); } return dp[n][k]; } }

// OJ: https://leetcode.com/problems/numberofwaystorearrangestickswithksticksvisible/ // Time: O(NK) // Space: O(Nk) long dp[1001][1001] = {}, fact[1001] = {}, mod = 1e9 + 7; class Solution { long dfs(int n, int k) { if (n < k) return 0; if (k == n) return 1; if (k == 1) return fact[n  1]; if (dp[n][k]) return dp[n][k]; long ans = 0; ans = (ans + dfs(n  1, k) * (n  1) % mod) % mod; ans = (ans + dfs(n  1, k  1)) % mod; return dp[n][k] = ans; } public: int rearrangeSticks(int n, int k) { memset(dp, 0, sizeof(dp)); fact[0] = 1; for (int i = 1; i <= n; ++i) { fact[i] = (fact[i  1] * i) % mod; // fact(n) = n! } return dfs(n, k); } };

# 1866. Number of Ways to Rearrange Sticks With K Sticks Visible # https://leetcode.com/problems/numberofwaystorearrangestickswithksticksvisible class Solution: @functools.lru_cache(None) def rearrangeSticks(self, n, k, M = 10**9 + 7): if n == k: return 1 if k == 0: return 0 return (self.rearrangeSticks(n  1, k  1) + self.rearrangeSticks(n  1, k) * (n  1)) % M