Number of Sets of K Non-Overlapping Line Segments LeetCode solution in Java

1
class Solution {
2
  Integer[][][] memo;
3
  int n;
4

5
  public int numberOfSets(int n, int k) {
6
    this.n = n;
7
    this.memo = new Integer[n + 1][k + 1][2];
8
    return dp(0, k, 1);
9
  }
10

11
  int dp(int i, int k, int isStart) {
12
    if (memo[i][k][isStart] != null) return memo[i][k][isStart];
13
    if (k == 0) return 1; // Found a way to draw k valid segments
14
    if (i == n) return 0; // Reach end of points
15

16
    int ans = dp(i + 1, k, isStart); // Skip ith point
17
    if (isStart == 1) ans += dp(i + 1, k, 0); // Take ith point as start
18
    else ans += dp(i, k - 1, 1); // Take ith point as end
19

20
    return memo[i][k][isStart] = ans % 1_000_000_007;
21
  }
22
}