5
\$\begingroup\$

I have solved Leetcode climbing-stairs problem which is stated as:

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.

I used dynamic programming to solve this like below:

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==1:
            return 1
        dp = [0 for i in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]
  1. Is there any improvement of this code?
  2. Is there any alternative way rather than dynamic programming?
\$\endgroup\$
  • 1
    \$\begingroup\$ Does the recursion formula remind you of some famous sequence? (Spoiler: codereview.stackexchange.com/questions/96197/…) \$\endgroup\$ – Martin R Oct 16 '17 at 19:42
  • \$\begingroup\$ @MartinR, yes. It shows a lot of ways. Thanks a lot for sharing. \$\endgroup\$ – arsho Oct 16 '17 at 21:08
4
\$\begingroup\$

Pythonic Ideas

Multiplication with lists

You can create an array of n + 1 zeros using the * operator:

dp = [0] * (n + 1)

Which seems a bit clearer (IMHO) than:

dp = [0 for i in range(n+1)]

General solution with no base case

You could get rid of the base case n == 1 if you do:

def climbStairs(self, n):
    """
    :type n: int
    :rtype: int
    """
    dp = [0] * max(3, n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Computing Fibonacci

Your solution is one of the fastest (and most obvious) ways to compute fibonacci with a running time of \$O(n)\$. However, there's a \$O(\log{}n)\$ solution using an interesting property of fibonacci numbers. Here's a proof and an in depth explanation.

Basically if you know F(n) and F(n-1) you can find F(2n) and F(2n-1) following these two formulas:

\begin{aligned}F_{2n-1}&=F_{n}^{2}+F_{n-1}^{2}\\F_{2n}&=(F_{n-1}+F_{n+1})F_{n}\\&=(2F_{n-1}+F_{n})F_{n}.\end{aligned}

Using this, you can double your way to the fibonacci number you need (or recursively half your way down)

def fibonacci(n):
    memo = {
        0: 0,
        1: 1,
        2: 1,
        3: 2
    }
    def recurse(n):
        if not n in memo:
            if n % 2 == 0:
                k = n // 2
                memo[k] = recurse(k)
                memo[k - 1] = recurse(k - 1)
                memo[n] = (2 * memo[k - 1] + memo[k]) * memo[k]
            else:
                k = (n + 1) // 2
                memo[k] = recurse(k)
                memo[k - 1] = recurse(k - 1)
                memo[n] = memo[k]**2 + memo[k -1]**2
        return memo[n]
    return recurse(n)

Note: While the closed form solution is interesting, it's not computationally practical since it requires infinate precision of \$\phi\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.