def climbStairs(self, n: int) -> int:
    res = ([(- 1)] * n)

    def dfs(n):
        if (n == 1):
            return 1
        if (n == 2):
            return 2
        if (res[(n - 1)] == (- 1)):
            res[(n - 1)] = (dfs((n - 1)) + dfs((n - 2)))
            return res[(n - 1)]
        else:
            return res[(n - 1)]
    ans = dfs(n)
    return ans
def climbStairs(self, n: int) -> int:
    res = ([(- 1)] * n)

    def dfs(n):
        if (n == 1):
            return 1
        if (n == 2):
            return 2
        if (res[(n - 1)] == (- 1)):
            res[(n - 1)] = (dfs((n - 1)) + dfs((n - 2)))
            return res[(n - 1)]
        else:
            return res[(n - 1)]
    ans = dfs(n)
    return ans