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

1
class Solution {
2
 public:
3
  int mod = 1e9 + 7;
4
  int dp[1011][1011][3];
5
  int f(int i, int k, int n, int ended) {
6
    if (k == 0) return 1;
7
    if (i == n) return 0;
8
    if (dp[i][k][ended] != -1) return dp[i][k][ended];
9
    int ans = 0;
10
    if (ended)
11
      ans = (ans + f(i + 1, k, n, 0) + f(i + 1, k, n, 1)) % mod;
12
    else
13
      ans = (ans + f(i + 1, k, n, 0) + f(i, k - 1, n, 1)) % mod;
14
    return dp[i][k][ended] = ans;
15
  }
16
  int numberOfSets(int n, int k) {
17
    memset(dp, -1, sizeof(dp));
18
    return f(0, k, n, 1);
19
  }
20
};