LeetCode 解題筆記：1621. Number of Sets of K Non-Overlapping Line Segments

作者：王一哲
日期：2026年9月16日


LeetCode 題目連結：1621. Number of Sets of K Non-Overlapping Line Segments

解題想法

中等難度題，題目給兩個整數 $n$ 與 $k$，代表共有 $n$ 個端點，端點編號為 $0$ 到 $n - 1$，計算以這 $n$ 個端點畫出不重疊的 $k$ 條線段共有幾種方法，由於答案很大，回傳值為方法數對 $10^9 + 7$ 取餘數。這題可以用動態規畫解題，定義長度為 $n+1$ 的一維陣列 $dp$，$dp[j]$ 代表畫出 $n$ 條線段的方法數，初始值為 1，因為畫出 $j$ 條線段至少有 $1$ 種畫法；另外 $dp[0] = 0$，因為畫出 $0$ 條線段的方法數為 $0$。為了縮短更新 $dp$ 內容需要的時間，另外開一個長度為 $n+1$ 的陣列 $psum$，$psum[i] = dp[0] + dp[1] + \dots + dp[i]$。用兩層 for 迴圈更新 $dp$，外層 for 迴圈跑線段數量 $j = 1$ 到 $j = k$，每次先開兩個長度為 $n+1$ 的陣列 new_dp, new_psum，用來儲存新的 dp 及前綴和；內層的 for 迴圈跑端點 $i = 2$ 到 $i = n$，狀態轉移的方式為不使用這個端點的方法數 + 使用這個端點當作右端點的方法數，同時還要更新新的方法數對應的前綴和，每次更新時都要對 $10^9 + 7$ 取餘數，更新完畢之後將 dp, new_dp 及 psum, new_psum 的資料交換。最後的答案會在 $dp[n]$。

Python 程式碼

Runtime: 517 ms, beats 48.28%. Memory: 19.52 MB, beats 55.17%.

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [1] * (n + 1)  # dp[j] 畫出 j 條線段的方法數
        dp[0] = 0  # 初始值，畫出 0 條，方法數 0
        psum = [i for i in range(n + 1)]  # dp[0] + ... + dp[i] 前綴和

        for j in range(1, k + 1):  # 畫 1 ~ k 條線段
            new_dp = [0] * (n + 1)  # 新的狀態
            new_psum = [0] * (n + 1)  # 新的前綴和
            for i in range(2, n + 1):  # 跑端點 2 ~ n
                # 狀態轉移，不使用這個端點 + 使用這個端點當作右端點的方法數
                new_dp[i] = (new_dp[i-1] + psum[i-1]) % MOD
                # 更新前綴和
                new_psum[i] = (new_psum[i-1] + new_dp[i]) % MOD
            # 交換資料
            dp = new_dp
            psum = new_psum
        return dp[n]

C++ 程式碼

Runtime: 47 ms, beats 57.01%. Memory: 51.49 MB, beats 38.78%.

class Solution {
public:
    int numberOfSets(int n, int k) {
        const int MOD = 1000000007;
        vector<int> dp (n+1, 1);  // dp[j] 畫出 j 條線段的方法數
        dp[0] = 0;  // 初始值，畫出 0 條，方法數 0
        vector<int> psum (n+1, 0);  // dp[0] + ... + dp[i] 前綴和
        iota(psum.begin(), psum.end(), 0);

        for(int j = 1; j <= k; j++) {  // 畫 1 ~ k 條線段
            vector<int> new_dp (n+1, 0);  // 新的狀態
            vector<int> new_psum (n+1, 0);  // 新的前綴和
            for(int i = 2; i <= n; i++) {  // 跑端點 2 ~ n
                // 狀態轉移，不使用這個端點 + 使用這個端點當作右端點的方法數
                new_dp[i] = (new_dp[i-1] + psum[i-1]) % MOD;
                // 更新前綴和
                new_psum[i] = (new_psum[i-1] + new_dp[i]) % MOD;
            }
            // 交換資料
            swap(dp, new_dp);
            swap(psum, new_psum);
        }
        return dp[n];
    }
};