BinarySearch 0985 Number of Monotonically Increasing Lists

Problem statement

https://binarysearch.com/problems/Number-of-Monotonically-Increasing-Lists/

Solution

Actually, what is asked is number of partitions P(n, k), which can be found with reccurent formula.

Complexity

It is O(nk) for time and space.

Code

class Solution:
    def solve(self, n, k):
        @lru_cache(None)
        def dp(n, k):
            if n < 0: return 0
            if k == 0: return (n == 0)
            return (dp(n - 1, k - 1) + dp(n - k, k)) % (10**9 + 7)

        if k == 1: return 1
        return dp(n, k)