Skip to content

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

  • Time: $O(nk)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int numberOfSets(int n, int k) {
    this->n = n;
    dp.resize(n, vector<vector<int>>(k + 1, vector<int>(2, -1)));
    return numberOfSets(0, k, /*drawing=*/false);
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  int n;
  vector<vector<vector<int>>> dp;

  int numberOfSets(int i, int k, bool drawing) {
    if (k == 0)  // Find a way to draw k segments.
      return 1;
    if (i == n)  // Reach the end.
      return 0;
    if (dp[i][k][drawing] != -1)
      return dp[i][k][drawing];
    if (drawing == 1)
      // (1) Keep drawing at i and move to i + 1.
      // (2) Stop at i so decrease k. We can start from i for the next segment.
      return dp[i][k][drawing] = (numberOfSets(i + 1, k, true) +
                                  numberOfSets(i, k - 1, false)) %
                                 kMod;
    // (1) Skip i and move to i + 1.
    // (2) Start at i and move to i + 1.
    return dp[i][k][drawing] = (numberOfSets(i + 1, k, false) +  //
                                numberOfSets(i + 1, k, true)) %
                               kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int numberOfSets(int n, int k) {
    this.n = n;
    dp = new Integer[n][k + 1][2];
    return numberOfSets(0, k, false);
  }

  private static final int kMod = 1_000_000_007;
  private int n;
  private Integer[][][] dp;

  private int numberOfSets(int i, int k, boolean drawing) {
    if (k == 0) // Find a way to draw k segments.
      return 1;
    if (i == n) // Reach the end.
      return 0;
    if (dp[i][k][drawing ? 1 : 0] != null)
      return dp[i][k][drawing ? 1 : 0];
    if (drawing)
      // (1) Keep drawing at i and move to i + 1.
      // (2) Stop at i so decrease k. We can start from i for the next segment.
      return dp[i][k][drawing ? 1 : 0] = (numberOfSets(i + 1, k, true) + //
                                          numberOfSets(i, k - 1, false)) %
                                         kMod;
    // (1) Skip i and move to i + 1.
    // (2) Start at i and move to i + 1.
    return dp[i][k][drawing ? 1 : 0] = (numberOfSets(i + 1, k, false) + //
                                        numberOfSets(i + 1, k, true)) %
                                       kMod;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def numberOfSets(self, n: int, k: int) -> int:
    kMod = 1_000_000_007

    @functools.lru_cache(None)
    def dp(i: int, k: int, drawing: bool) -> int:
      if k == 0:  # Find a way to draw k segments.
        return 1
      if i == n:  # Reach the end.
        return 0
      if drawing:
        # (1) Keep drawing at i and move to i + 1.
        # (2) Stop at i so decrease k. We can start from i for the next segment.
        return (dp(i + 1, k, True) + dp(i, k - 1, False)) % kMod
      # (1) Skip i and move to i + 1.
      # (2) Start at i and move to i + 1.
      return (dp(i + 1, k, False) + dp(i + 1, k, True)) % kMod

    return dp(0, k, False)