Medium

题目描述

给定一维平面上的 n 个点，其中第 i 个点（从 0 到 n-1）位于 x = i 处，找到我们可以恰好画出 k 个不重叠线段的方法数，使得每个线段覆盖两个或更多点。每个线段的端点必须具有整数坐标。k 个线段不必覆盖所有 n 个点，并且它们可以共享端点。

返回我们可以画出 k 个不重叠线段的方法数。由于这个数字可能很大，请将其模 10^9 + 7 返回。

示例 1：

输入：n = 4, k = 2
输出：5
解释：两条线段分别用红色和蓝色显示。
上图显示了5种不同的方式：{(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}。

示例 2：

输入：n = 3, k = 1
输出：3
解释：3种方式是 {(0,1)}, {(0,2)}, {(1,2)}。

示例 3：

输入：n = 30, k = 7
输出：796297179
解释：画7条线段的可能方式总数为3796297200。取模 10^9 + 7 得到 796297179。

约束条件：

  • 2 <= n <= 1000
  • 1 <= k <= n-1

解题思路

这道题可以用动态规划来解决。核心思想是考虑每个点的状态：是否在某个线段的内部，以及已经放置了多少个线段。

状态定义：

  • dp[i][j][flag] 表示考虑前 i 个点，已放置 j 个线段，flag 表示当前是否处于线段内部的方案数
  • flag = 0：当前不在任何线段内部
  • flag = 1：当前在某个线段内部（已有起点但未确定终点）

状态转移： 对于每个位置 i，我们有以下选择：

  1. 如果 flag = 0（当前不在线段内）：

    • 不做任何操作：dp[i+1][j][0] += dp[i][j][0]
    • 在位置 i 开始新线段：dp[i+1][j][1] += dp[i][j][0]

  2. 如果 flag = 1（当前在线段内）：

    • 继续延长当前线段：dp[i+1][j][1] += dp[i][j][1]
    • 在位置 i 结束当前线段：dp[i+1][j+1][0] += dp[i][j][1]
    • 在位置 i 结束当前线段并开始新线段：dp[i+1][j+1][1] += dp[i][j][1]

这种方法的时间复杂度为 O(n²k)，但可以优化为 O(nk)。实际上，这个问题还有组合数学的解法，答案为 C(n+k-1, 2k)。

代码实现

class Solution {
public:
    int numberOfSets(int n, int k) {
        const int MOD = 1e9 + 7;
        // dp[i][j][flag] - 考虑前i个点，放置j个线段，flag表示是否在线段内
        // flag=0: 不在线段内, flag=1: 在线段内
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(k + 1, vector<long long>(2, 0)));
        
        dp[0][0][0] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                // 当前不在线段内
                dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % MOD; // 不操作
                dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][0]) % MOD; // 开始新线段
                
                // 当前在线段内
                dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][1]) % MOD; // 继续线段
                if (j + 1 <= k) {
                    dp[i + 1][j + 1][0] = (dp[i + 1][j + 1][0] + dp[i][j][1]) % MOD; // 结束线段
                    dp[i + 1][j + 1][1] = (dp[i + 1][j + 1][1] + dp[i][j][1]) % MOD; // 结束并开始新线段
                }
            }
        }
        
        return dp[n][k][0];
    }
};

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        # dp[i][j][flag] - 考虑前i个点，放置j个线段，flag表示是否在线段内
        # flag=0: 不在线段内, flag=1: 在线段内
        dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n + 1)]
        
        dp[0][0][0] = 1
        
        for i in range(n):
            for j in range(k + 1):
                # 当前不在线段内
                dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % MOD  # 不操作
                dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][0]) % MOD  # 开始新线段
                
                # 当前在线段内
                dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][1]) % MOD  # 继续线段
                if j + 1 <= k:
                    dp[i + 1][j + 1][0] = (dp[i + 1][j + 1][0] + dp[i][j][1]) % MOD  # 结束线段
                    dp[i + 1][j + 1][1] = (dp[i + 1][j + 1][1] + dp[i][j][1]) % MOD  # 结束并开始新线段
        
        return dp[n][k][0]

public class Solution {
    public int NumberOfSets(int n, int k) {
        const int MOD = 1000000007;
        // dp[i][j][flag] - 考虑前i个点，放置j个线段，flag表示是否在线段内
        // flag=0: 不在线段内, flag=1: 在线段内
        long[,,] dp = new long[n + 1, k + 1, 2];
        
        dp[0, 0, 0] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                // 当前不在线段内
                dp[i + 1, j, 0] = (dp[i + 1, j, 0] + dp[i, j, 0]) % MOD; // 不操作
                dp[i + 1, j, 1] = (dp[i + 1, j, 1] + dp[i, j, 0]) % MOD; // 开始新线段
                
                // 当前在线段内
                dp[i + 1, j, 1] = (dp[i + 1, j, 1] + dp[i, j, 1]) % MOD; // 继续线段
                if (j + 1 <= k) {
                    dp[i + 1, j + 1, 0] = (dp[i + 1, j + 1, 0] + dp[i, j, 1]) % MOD; // 结束线段
                    dp[i + 1, j + 1, 1] = (dp[i + 1, j + 1, 1] + dp[i, j, 1]) % MOD; // 结束并开始新线段
                }
            }
        }
        
        return (int)dp[n, k, 0];
    }
}

var numberOfSets = function(n, k) {
    const MOD = 1000000007;
    // dp[i][j][flag] - 考虑前i个点，放置j个线段，flag表示是否在线段内
    // flag=0: 不在线段内, flag=1: 在线段内
    const dp = Array(n + 1).fill().map(() => 
        Array(k + 1).fill().map(() => Array(2).fill(0))
    );
    
    dp[0][0][0] = 1;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= k; j++) {
            // 当前不在线段内
            dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % MOD; // 不操作
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][0]) % MOD; // 开始新线段
            
            // 当前在线段内
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][1]) % MOD; // 继续线段
            if (j + 1 <= k) {
                dp[i + 1][j + 1][0] = (dp[i + 1][j + 1][0] + dp[i][j][1]) % MOD; // 结束线段
                dp[i + 1][j + 1][1] = (dp[i + 1][j + 1][1] + dp[i][j][1]) % MOD; // 结束并开始新线段
            }
        }
    }
    
    return dp[n][k][0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
动态规划O(n × k)O(n × k)