Leetcode Problem 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

1866. Number of Ways to Rearrange Sticks With K Sticks Visible

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a 2D DP array dp with dimensions (n+1) x (k+1) and fill it with -1 to indicate uncomputed values.
  2. Define a recursive function numWays(n, k) that returns the number of ways to arrange n sticks such that k are visible.
  3. If k is 0 or greater than n, return 0 as it's not possible to have such an arrangement.
  4. If n is 1 or k is 1, return 1 as there's only one way to arrange them.
  5. If dp[n][k] is not -1, return the cached value.
  6. Calculate the number of ways by choosing the tallest stick and solve the subproblem (n-1, k-1).
  7. Calculate the number of ways by choosing any other stick and solve the subproblem (n-1, k), multiplied by (n-1).
  8. Sum the two calculated values and take modulo 10^9 + 7 to prevent overflow.
  9. Store the result in dp[n][k] and return it.
  10. Call numWays(n, k) from the main function and return the result.
UML Thumbnail

Backtracking Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...