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

1
class Solution:
2
    def numberOfSets(self, n: int, k: int) -> int:
3
        MOD = 10**9 + 7
4

5
        @lru_cache(None)
6
        def dp(i, k, isStart):
7
            if k == 0:
8
                return 1  # Found a way to draw k valid segments
9
            if i == n:
10
                return 0  # Reach end of points
11
            ans = dp(i + 1, k, isStart)  # Skip ith point
12
            if isStart:
13
                ans += dp(i + 1, k, False)  # Take ith point as start
14
            else:
15
                ans += dp(i, k - 1, True)  # Take ith point as end
16
            return ans % MOD
17

18
        return dp(0, k, True)