1621.-number-of-sets-of-k-non-overlapping-line-segments.md

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

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        dp = [[[0,0] for _ in range(k + 1)] for i in range(n)]
        print(dp)
        dp[0][0][0] = 1
        mod = 10**9+7
        for i in range(1,n):
            for j in range(k + 1):  
                ## 最后为零就是不到边界 
                ## 为上一个长度的结果 
                dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1])%mod
                dp[i][j][1] = dp[i-1][j][1]
                
                if j > 0:
                    dp[i][j][1] += dp[i-1][j-1][0]
                    dp[i][j][1] %=mod
                    dp[i][j][1] += dp[i-1][j-1][1]
                    dp[i][j][1] %=mod
                    
        return (dp[n-1][k][0] + dp[n-1][k][1])%mod