lc-1621-number-of-sets-of-k-non-overlapping-line-segments.org

LC 1621. 大小为 K 的不重叠线段的数目

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

很容易看出是动态规划，但是直接写就会出现超时。原因是简单的动态规划时间复杂度是O(n^3). 不过先写出简单的动态规划实现对推导很有帮助。

下面是简单的动态规划实现，可以列出状态方程

• F(x, k) 表示已x为起点，选择k个不重叠的线段组合数
• F(x, k) = F(x+1, k-1) + 2*F(x+2, k-1) + 3*F(x+3, k-1) + …

其实只要观察到类似 `m*F(x+m, k-1)` 这种表达式，基本上就可以确定需要经过某种变化，否则会出现重复计算，时间复杂度会上升。

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        MOD = 10 ** 9 + 7
        dp = {}

        def fun(x, k):
            if k == 0:
                return 1

            key = (x, k)
            if key in dp: return dp[key]
            ans = 0
            for y in range(x + 1, n):
                # [x, y] is available
                # there are y - x solutions.
                sz = y - x
                ans += sz * fun(y, k - 1)
            ans = ans % MOD
            dp[key] = ans
            return ans

        ans = fun(0, k)
        return ans

上面是基于记忆的方式求解动态规划，这种实现不太好做变换，做变换最好还是基于迭代的实现方式。换个状态方程：

• F(x, k) 表示以x为终点，选择k个不重叠的线段组合数
• F(x, k) = F(x-1, k-1) + 2*F(x-2, k-1) + …
• 所以 `F(x+1, k)-F(x, k)=F(x, k-1)+F(x-1, k-1)+F(x-2, k-1)+…`
• 然后基本状态是F(x, 1)=x

实现上为了节省空间可以使用滚动数组，为了方便阅读我还是粘贴直接实现的方式。

class Solution2:
    def numberOfSets(self, n: int, k: int) -> int:
        MOD = 10 ** 9 + 7
        dp = [[0] * n for _ in range(k + 1)]

        # dp[k][x] 以 x结束，可以分为k段的组合数
        for i in range(n):
            dp[1][i] = i

        for kk in range(2, k + 1):
            acc = 0
            for i in range(n - 1):
                acc += dp[kk - 1][i]
                dp[kk][i + 1] = dp[kk][i] + acc

        ans = 0
        for i in range(n):
            ans += dp[k][i]
        return ans % MOD