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

Scan points right-to-left; dp[i][j] counts ways to place j segments using points i..n-1, and a suffix sum collapses the 'where does the next segment start' choice into O(1).

Idea

Define dp[i][j] = number of ways to draw j non-overlapping segments using only the points i, i+1, ..., n-1. The answer is dp[0][k].

Look at point i and ask what role it plays:

1. Point i is not the left endpoint of any segment. Then everything happens among points i+1..n-1, giving dp[i+1][j] ways.
2. Point i is the left endpoint of a segment. The segment runs from i to some point p with i < p <= n-1. Because segments may share endpoints, the remaining j-1 segments live among points p..n-1 (point p can be reused). That contributes sum over p in [i+1, n-1] of dp[p][j-1].

So:

dp[i][j] = dp[i+1][j] + sum_{p=i+1}^{n-1} dp[p][j-1]

with base case dp[i][0] = 1 (one way to draw zero segments).

Making it O(n·k)

The inner sum would make this O(n^2 * k). Keep a suffix sum suf[i][j] = sum_{p=i}^{n-1} dp[p][j]. Then the recurrence becomes:

dp[i][j] = dp[i+1][j] + suf[i+1][j-1]
suf[i][j] = suf[i+1][j] + dp[i][j]

Each cell is now O(1).

Walk-through (n = 4, k = 2)

Points are 0,1,2,3. Base row dp[i][0] = 1 for all i.

Fill j = 1 (one segment), right to left:

• dp[3][1] = 0 — a single point can't form a segment.
• dp[2][1] = dp[3][1] + suf[3][0] = 0 + 1 = 1 — segment {2,3}.
• dp[1][1] = dp[2][1] + suf[2][0] = 1 + 2 = 3 — {1,2}, {1,3}, {2,3}.
• dp[0][1] = dp[1][1] + suf[1][0] = 3 + 3 = 6 — six single segments total.

Fill j = 2 (two segments):

• dp[3][2] = 0, dp[2][2] = 0 — not enough room.
• dp[1][2] = dp[2][2] + suf[2][1] = 0 + (1+0) = 1.
• dp[0][2] = dp[1][2] + suf[1][1] = 1 + (3+1+0) = 5.

So dp[0][2] = 5, matching the five drawings {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Note

There is a slick closed form, C(n + k - 1, 2k) mod (10^9 + 7), but the DP above generalises the reasoning and is what the visualizer animates.

Complexity

• Time: O(n·k)
• Space: O(n·k) (reducible to O(n) with rolling rows)

class Solution {
    public int numberOfSets(int n, int k) {
        final int MOD = 1_000_000_007;
        // dp[i][j] = ways to draw j segments using points i..n-1
        // suf[i][j] = sum_{p=i}^{n-1} dp[p][j]
        long[][] dp = new long[n + 1][k + 1];
        long[][] suf = new long[n + 1][k + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = (dp[i + 1][j] + suf[i + 1][j - 1]) % MOD;
            }
            for (int j = 0; j <= k; j++) {
                suf[i][j] = (suf[i + 1][j] + dp[i][j]) % MOD;
            }
        }
        return (int) (dp[0][k] % MOD);
    }
}