Climbing Stairs

  # ----------------------------------------
  # 1. Climbing Stairs - Basic DP Introduction
  #
  # Problem: You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps.
  # How many distinct ways can you climb to the top?
  #
  # Input: n = 3
  # Output: 3 (1+1+1, 1+2, 2+1)
  #
  # Time Complexity: O(n)
  # Space Complexity: O(1)
  # ----------------------------------------
  def climbing_stairs(n)
    return 1 if n <= 1
    
    prev2, prev1 = 1, 1
    
    (2..n).each do |i|
      current = prev1 + prev2
      puts "Step #{i}: ways = #{prev1} + #{prev2} = #{current}"
      prev2, prev1 = prev1, current
    end
    
    puts "Total ways to climb #{n} stairs: #{prev1}"
    prev1