###### tags: `Week_2`, `Dynamic Programming`

# Dynamic Programming

## 509. [Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)

class Solution:
    def fib(self, n: int) -> int:
        
        if n <= 1:
            return n

        dp = [0 for _ in range(n+1)]
        
        dp[0] = 0
        dp[1] = 1
        
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
            
        return dp[-1]

## 70. [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)

class Solution:
    def climbStairs(self, n: int) -> int:
        
        if n <= 2:
            return n
        
        current = 0
        prev1 = 2
        prev2 = 1
        
        for i in range(3, n+1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
    
        return current