Problem Description

You are given two integers, n and k. There are n+1 points labeled from 0 to n on a 1-dimensional line. Your task is to count the number of ways to select k non-overlapping line segments such that:

• Each segment connects two distinct points (i, j) where 0 <= i < j <= n.
• No two segments share any point (segments are non-overlapping).
• Segments can share endpoints, but cannot overlap in any other way (i.e., no point is contained in more than one segment).

Return the number of possible sets of k non-overlapping segments, modulo 10^9 + 7.

Constraints:

• 1 <= n <= 1000
• 1 <= k <= n

Thought Process

At first glance, the problem seems to ask us to enumerate all possible ways to pick k segments from n+1 points, making sure they don't overlap. A brute-force approach would try every possible combination, but with n up to 1000, this quickly becomes infeasible.

Instead, let's look for patterns and relationships. The key insight is to realize that each segment "uses up" two points, and since they cannot overlap, the segments must be separated. We need to count the ways to pick k pairs of points such that no two pairs overlap.

This leads us to dynamic programming, where we build up the answer for smaller values of n and k, and use the results to solve larger ones.

Solution Approach

We use dynamic programming to solve the problem efficiently. Let's define dp[i][j] as the number of ways to draw j non-overlapping segments among the first i points (i.e., points 0 to i).

• Base Case: dp[i][0] = 1 for all i, since there is 1 way to draw 0 segments (do nothing).
• Transition: For dp[i][j], we consider two cases:
  • We do not use the i-th point: dp[i-1][j]
  • We use the i-th point as the right endpoint of a new segment. The left endpoint can be any point l where 0 <= l < i. For each such l, the number of ways to draw j-1 segments among the first l points is dp[l][j-1]. So, sum over all l:
  • sum_{l=0}^{i-1} dp[l][j-1]

  The total is: dp[i][j] = dp[i-1][j] + sum_{l=0}^{i-1} dp[l][j-1]

• Optimization: To compute sum_{l=0}^{i-1} dp[l][j-1] efficiently, we use prefix sums.
• Final Answer: dp[n][k] is the number of ways to choose k non-overlapping segments among n+1 points.

We perform all operations modulo 10^9 + 7 as required.

Example Walkthrough

Let's take n = 4, k = 2 (points 0, 1, 2, 3, 4).

1. Possible segments: (0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
2. We need to pick 2 non-overlapping segments:
   • For example, (0,1) and (2,3) is valid (no shared points).
   • (0,2) and (2,3) is not valid (they share point 2).
3. Using DP:
   • We fill dp[i][j] for all i up to 4 and j up to 2.
   • For dp[4][2], we combine ways to draw 2 segments among 5 points.
4. Final answer: dp[4][2] = 6 (as per Leetcode's example).

Time and Space Complexity

• Brute-force: Enumerating all possible sets of k non-overlapping segments would be exponential in n, i.e., O(C(n^2, k)), which is infeasible for n=1000.
• Optimized DP:
  • There are O(nk) subproblems (dp[i][j] for i in 0..n and j in 0..k).
  • Each dp[i][j] can be computed in O(1) time using prefix sums.
  • Total time complexity: O(nk)
  • Space complexity: O(nk) for the DP table.

Summary

This problem is a classic example of combinatorial dynamic programming. By breaking the problem into overlapping subproblems and carefully managing transitions (with prefix sums for efficiency), we can solve it in polynomial time. The main insight is to realize that picking non-overlapping segments is equivalent to partitioning the points and counting valid configurations recursively. This DP approach is both elegant and efficient, and demonstrates the power of recursive thinking and memoization in combinatorial problems.

Code Implementation

MOD = 10**9 + 7

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = 1

        for segs in range(1, k + 1):
            prefix = [0] * (n + 2)
            for i in range(n + 1):
                prefix[i + 1] = (prefix[i] + dp[i][segs - 1]) % MOD
            for i in range(1, n + 1):
                dp[i][segs] = (dp[i - 1][segs] + prefix[i]) % MOD
        return dp[n][k]
      

const int MOD = 1e9 + 7;

class Solution {
public:
    int numberOfSets(int n, int k) {
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        for (int i = 0; i <= n; ++i) dp[i][0] = 1;
        for (int segs = 1; segs <= k; ++segs) {
            vector<int> prefix(n + 2, 0);
            for (int i = 0; i <= n; ++i)
                prefix[i + 1] = (prefix[i] + dp[i][segs - 1]) % MOD;
            for (int i = 1; i <= n; ++i)
                dp[i][segs] = (dp[i - 1][segs] + prefix[i]) % MOD;
        }
        return dp[n][k];
    }
};
      

class Solution {
    static final int MOD = 1000000007;
    public int numberOfSets(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i <= n; ++i) dp[i][0] = 1;
        for (int segs = 1; segs <= k; ++segs) {
            int[] prefix = new int[n + 2];
            for (int i = 0; i <= n; ++i)
                prefix[i + 1] = (prefix[i] + dp[i][segs - 1]) % MOD;
            for (int i = 1; i <= n; ++i)
                dp[i][segs] = (dp[i - 1][segs] + prefix[i]) % MOD;
        }
        return dp[n][k];
    }
}
      

var numberOfSets = function(n, k) {
    const MOD = 1e9 + 7;
    const dp = Array.from({length: n + 1}, () => Array(k + 1).fill(0));
    for (let i = 0; i <= n; ++i) dp[i][0] = 1;
    for (let segs = 1; segs <= k; ++segs) {
        const prefix = Array(n + 2).fill(0);
        for (let i = 0; i <= n; ++i)
            prefix[i + 1] = (prefix[i] + dp[i][segs - 1]) % MOD;
        for (let i = 1; i <= n; ++i)
            dp[i][segs] = (dp[i - 1][segs] + prefix[i]) % MOD;
    }
    return dp[n][k];
};