Leetcode Problem 1621. Number of Sets of K Non-Overlapping Line Segments

1621. Number of Sets of K Non-Overlapping Line Segments

Leetcode Solutions

Dynamic Programming with Cumulative Sum Optimization

  1. Initialize a 2D DP array dp with dimensions n x (k+1) and a cumulative sum array cumulativeSum with the same dimensions, both filled with zeros.
  2. Set dp[i][0] to 1 for all i because there is always 1 way to draw 0 segments.
  3. Iterate over the points from 2 to n (1-indexed).
  4. For each point i, iterate over the number of segments j from 1 to k.
  5. Update dp[i][j] by adding the number of ways to draw j segments using i-1 points and the cumulative sum of ways to draw j-1 segments up to point i-1.
  6. Update the cumulative sum array with the new value of dp[i][j].
  7. The answer is dp[n][k] modulo 1e9+7.
UML Thumbnail

Combinatorics Approach Using Stars and Bars Theorem

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...