Leetcode 1725 Solution

This article provides solution to leetcode question 1725 (number-of-sets-of-k-non-overlapping-line-segments)
Categories:
Tags:
Access this page by simply typing in "lcs 1725" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/number-of-sets-of-k-non-overlapping-line-segments

Solution

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
        dp2 = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

        for i in range(n + 1):
            dp[i][0] = 1 if i > 0 else 0
            dp2[i][0] = dp2[i - 1][0] + 1 if i > 0 else 0

        for i in range(2, n + 1):
            for j in range(1, k + 1):
                dp[i][j] = (dp[i - 1][j] + dp2[i - 1][j - 1]) % 1000000007

                dp2[i][j] = dp2[i - 1][j] + dp[i][j]

        return dp[n][k]