BinarySearch 0634 A Flight of Stairs Sequel

Problem statement

https://binarysearch.com/problems/A-Flight-of-Stairs-Sequel/

Solution

Let dp(n, k) is number of ways, then we can use dp here.

Complexity

Time and space is O(nk).

Code

class Solution:
    def solve(self, n, k):
        @lru_cache(None)
        def dp(n, k):
            if k < 0: return 0
            if n < 0: return 0
            if n == 0: return 1
            return dp(n - 1, k) + dp(n - 2, k) + dp(n - 3, k - 1)

        return dp(n, k)