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

class Solution {
    public int numberOfSets(int n, int k) {
        long MOD = 1_000_000_007;
        int total = n + k - 1;
        int choose = 2 * k;
        return (int) combination(total, choose, MOD);
    }
    private long combination(int n, int r, long MOD) {
        if (r > n) return 0;
        long[][] dp = new long[n + 1][r + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, r); j++) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
            }
        }
        return dp[n][r];
    }
}

class Solution:
    def numberOfSets(self, n, k):
        MOD = 1_000_000_007

        total = n + k - 1
        choose = 2 * k

        return self.combination(total, choose, MOD)

    def combination(self, n, r, MOD):
        if r > n:
            return 0

        dp = [[0] * (r + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            dp[i][0] = 1

        for i in range(1, n + 1):
            for j in range(1, min(i, r) + 1):
                dp[i][j] = (
                    dp[i - 1][j - 1] +
                    dp[i - 1][j]
                ) % MOD

        return dp[n][r]

class Solution {
public:
    int numberOfSets(int n, int k) {
        const long long MOD = 1'000'000'007;

        int total = n + k - 1;
        int choose = 2 * k;

        return combination(total, choose, MOD);
    }

private:
    long long combination(int n, int r, long long MOD) {
        if (r > n)
            return 0;

        vector<vector<long long>> dp(
            n + 1,
            vector<long long>(r + 1, 0)
        );

        for (int i = 0; i <= n; i++)
            dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(i, r); j++) {
                dp[i][j] =
                    (dp[i - 1][j - 1] +
                     dp[i - 1][j]) % MOD;
            }
        }

        return dp[n][r];
    }
};

class Solution {
    numberOfSets(n, k) {
        const MOD = 1000000007;

        const total = n + k - 1;
        const choose = 2 * k;

        return this.combination(total, choose, MOD);
    }

    combination(n, r, MOD) {
        if (r > n) {
            return 0;
        }

        const dp = Array.from(
            { length: n + 1 },
            () => Array(r + 1).fill(0)
        );

        for (let i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= Math.min(i, r); j++) {
                dp[i][j] =
                    (dp[i - 1][j - 1] +
                     dp[i - 1][j]) % MOD;
            }
        }

        return dp[n][r];
    }
}