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

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

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

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

其实只要观察到类似 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

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

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

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