Range Sum Query - Immutable

Problem: Range Sum Query

We can use dynamic programming to solve the problem. At each position we store sum of all the numbers before it. So that when we are asked range sum we can answer quickly by subtracting two numbers.

Code in Python:

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1, 1]

        for i in xrange(2, n+1):
            dp.append(dp[i-2]+dp[i-1])
        return dp[n]