BinarySearch - Increasing Subsequences of Size K

[https://binarysearch.com/problems/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& 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; } ```