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
class Solution {
 public:
  int numberOfSets(int n, int k) {
    vector<vector<vector<int>>> mem(
        n, vector<vector<int>>(k + 1, vector<int>(2, -1)));
    return numberOfSets(0, k, /*drawing=*/false, n, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  int numberOfSets(int i, int k, bool drawing, int n,
                   vector<vector<vector<int>>>& mem) {
    if (k == 0)  // Find a way to draw k segments.
      return 1;
    if (i == n)  // Reach the end.
      return 0;
    if (mem[i][k][drawing] != -1)
      return mem[i][k][drawing];
    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 mem[i][k][drawing] = (numberOfSets(i + 1, k, true, n, mem) +
                                   numberOfSets(i, k - 1, false, n, mem)) %
                                  kMod;
    // 1. Skip i and move to i + 1.
    // 2. Start at i and move to i + 1.
    return mem[i][k][drawing] = (numberOfSets(i + 1, k, false, n, mem) +
                                 numberOfSets(i + 1, k, true, n, mem)) %
                                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
class Solution {
  public int numberOfSets(int n, int k) {
    Integer[][][] mem = new Integer[n][k + 1][2];
    return numberOfSets(0, k, /*drawing=*/false, n, mem);
  }

  private static final int kMod = 1_000_000_007;

  private int numberOfSets(int i, int k, boolean drawing, int n, Integer[][][] mem) {
    if (k == 0) // Find a way to draw k segments.
      return 1;
    if (i == n) // Reach the end.
      return 0;
    if (mem[i][k][drawing ? 1 : 0] != null)
      return mem[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 mem[i][k][drawing ? 1 : 0] = (numberOfSets(i + 1, k, true, n, mem) + //
                                           numberOfSets(i, k - 1, false, n, mem)) %
                                          kMod;
    // 1. Skip i and move to i + 1.
    // 2. Start at i and move to i + 1.
    return mem[i][k][drawing ? 1 : 0] = (numberOfSets(i + 1, k, false, n, mem) + //
                                         numberOfSets(i + 1, k, true, n, mem)) %
                                        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)