Problem statement

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

Solution 1

Define by dp[i] is number of subsequenes ending at A[i] which have k terms. Then we can increase k bo one if we use classical O(n^2) dp: the number of ways with k + 1 terms which end with A[j] can be calculated as sum over all dp[i], where i < j, and A[i] < A[j].

Complexity

It is O(n^2 k) for time and O(n) for space.

Code

class Solution:
    def solve(self, A, k):
        MOD, n = 10 ** 9 + 7, len(A)
        dp = [1] * n
        for k in range(k - 1):
            dp2 = [0] * n
            for j in range(n - 1, -1, -1):
                for i in range(j):
                    if A[i] < A[j]:
                        dp2[j] += dp[i]
            dp = [x % MOD for x in dp2]

        return sum(dp) % MOD

Solution 2

There is a better solution. The trick is to keep k binary indexed trees. We add element by element, starting from the smallest values and in dp[j][t] we keep number of Increasing subsequences of length j, which ends with A[t] element. When we add each next greater element, we can use our binary indexed trees to quickly find all smaller elements, instead of O(n), we can do it in O(log n) time.

Complexity

It is O(n log n k) for time and O(n*k) for space.

Code

class BIT:
    def __init__(self, n):
        self.sums = [0] * (n+1)

    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] = (self.sums[i] + delta) % (10**9 + 7)
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res = (res + self.sums[i]) % (10**9 + 7)
            i -= i & (-i)
        return res

class Solution:
    def solve(self, A, k):
        n = len(A)
        dp = [BIT(n) for i in range(k)]
        arr = sorted([(x, i) for i, x in enumerate(A)])
        d = {x: i for i, x in enumerate(sorted(A))}

        for i in range(n):
            idx = d[A[i]]
            for j in range(k - 1):
                dp[j].update(idx + 1, dp[j + 1].query(idx))
            dp[k - 1].update(idx + 1, 1)

        return dp[0].query(n)