Dynamic Programming Practice: Fibonacci, Climbing Stairs, and Minimum Cost
Fibonacci Number (LeetCode 509)
The Fibonacci seqeunce is defined as:
F(0) = 0F(1) = 1F(n) = F(n - 1) + F(n - 2)forn > 1
Example:
- Input:
n = 4 - Output:
3(Sequence: 0, 1, 1, 2, 3)
Solution using constant space:
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
# Initialize the first two values
a, b = 0, 1
# Iterate to calculate the nth value
for _ in range(2, n + 1):
next_val = a + b
a = b
b = next_val
return b
Climbing Stairs (LeetCode 70)
You are climbing a staircase with n steps. Each time you can climb either 1 or 2 steps. Calculate the distinct number of ways to reach the top.
Example:
- Input:
n = 3 - Output:
3(Ways: 1+1+1, 1+2, 2+1)
Solution using optimized state variables:
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
# Ways to reach the previous two steps
ways_prev = 1
ways_curr = 2
for _ in range(3, n + 1):
total_ways = ways_prev + ways_curr
ways_prev = ways_curr
ways_curr = total_ways
return ways_curr
Min Cost Climbing Stairs (LeetCode 746)
Given an array cost where cost[i] is the price to pay to step from the i-th stair. You can climb 1 or 2 steps after paying. Find the minimum cost to reach the top (beyond the last index). You may start from index 0 or 1.
Example:
- Input:
cost = [10, 15, 20] - Output:
15(Start at index 1, pay 15, then take two steps to the top)
Solution:
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
# Initialize cost to reach the first two steps
step_one_back = 0
step_two_back = 0
for i in range(2, len(cost) + 1):
# Cost to get to current position i is min of:
# 1. Coming from i-2 (step_two_back + cost[i-2])
# 2. Coming from i-1 (step_one_back + cost[i-1])
current_min_cost = min(step_two_back + cost[i - 2], step_one_back + cost[i - 1])
# Shift variables for the next iteration
step_two_back = step_one_back
step_one_back = current_min_cost
return step_one_back
