LeetCode 1621: Number of Sets of K Non-Overlapping Line Segments
Problem Description
Explanation:
The problem can be solved using dynamic programming. We can define a 3D DP array dp where dp[i][j][l] represents the number of ways to draw l non-overlapping line segments using the first i points, with the jth point as the last point of the last segment.
For each dp[i][j][l], we can either:
- Extend the last segment to include point
i, increasing the count bydp[i-1][j][l]. - Start a new segment at point
i, increasing the count bydp[i-1][i-1][l-1].
The final result will be the sum of dp[n-1][j][k] for j from 0 to n-1.
Solutions
class Solution {
public int numberOfSets(int n, int k) {
int mod = 1000000007;
int[][][] dp = new int[n][n][k+1];
for (int i = 0; i < n; i++) {
dp[i][i][1] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int l = 1; l <= k; l++) {
dp[i][j][l] = (dp[i-1][j][l] + dp[i-1][i-1][l-1]) % mod;
}
}
}
int res = 0;
for (int j = 0; j < n; j++) {
res = (res + dp[n-1][j][k]) % mod;
}
return res;
}
}Loading editor...