BinarySearch - Increasing Subsequences of Size K

https://binarysearch.com/problems/Increasing-Subsequences-of-Size-K

Problem

Given a list of integers nums and an integer k, return the number of subsequences of size k that are strictly increasing.

Mod the result by 10 ** 9 + 7.

Constraints

0 ≤ n ≤ 1,000 where n is the length of nums. 1 ≤ k ≤ 10

Solution

Use Dynamic Programming.

Define dp[i][j] to store the count of increasing subsequences of size i ending with element nums[j].

$dp[i][j] = 1$, where $i = 1$ and $1 <= j <= n$

$dp[i][j] = dp[i][j] + dp[i - 1][j]$, where $1 < i <= k$, $i <= j <= n$ and $nums[m] < nums[j]$ for $(i - 1) <= m < j$.

Time Complexity: $O(k * n ^ 2)$

Space Complexity: $O(k * n)$

int solve(vector<int>& nums, int k) {
    int n = (int)nums.size(), dp[k][n], ans = 0, mod = 1e9 + 7;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) dp[0][i] = 1;
    for (int l = 1; l < k; l++) {
        for (int i = l; i < n; i++) {
            dp[l][i] = 0;
            for (int j = l - 1; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[l][i] = (dp[l][i] + dp[l - 1][j]) % mod;
                }
            }
        }
    }
    for (int i = k - 1; i < n; i++) {
        ans = (ans + dp[k - 1][i]) % mod;
    }
    return ans;
}