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

Given n points on a 1-D plane, where the ith point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 109 + 7.

class Solution {
    int dp[1001][1001];
    int mod = 1e9 + 7;
public:
    int numberOfSets(int n, int k) {
        if(!k) return 1;
        if(n < k + 1) return 0;
        if(!dp[n][k]) {
            dp[n][k] = 1 + numberOfSets(n-1, k) % mod;
            for(int i = n; i > k; i--) {
                dp[n][k] = (dp[n][k] + numberOfSets(i-1, k-1)) % mod;
            }
        }
        return dp[n][k] - 1;
    }
};