Dynamic Programming | Coding Interview Preparation | 1D Array

Coding Round Questions:

Climbing Stairs

function climbStairs(n) {
  if (n === 0) return 1; // Base case: One way to stay at the ground
  if (n < 0) return 0;   // Invalid step
  return climbStairs(n - 1) + climbStairs(n - 2); // Recursive case
}

// Test cases
console.log(climbStairs(3)); // 3
console.log(climbStairs(4)); // 5
console.log(climbStairs(5)); // 8

Min Cost Climbing Stairs OR Maximum Sum of Non-Adjacent Elements

                          Math.min(minCost(2), minCost(1))
                          /                          \
          minCost(2)                                 minCost(1)
           |                                           |
   20 + min(minCost(1), minCost(0))                   cost[1] = 15
           /              \
     minCost(1)       minCost(0)
         |                |
     cost[1] = 15     cost[0] = 10

function minCost(cost, n) {
  if (n < 0) return 0; // Base case: No cost for invalid step
  if (n === 0 || n === 1) return cost[n]; // Base cases: Direct cost
  return cost[n] + Math.min(minCost(cost, n - 1), minCost(cost, n - 2)); // Recursive case
}

// Test cases
const cost = [10, 15, 20];
console.log(Math.min(minCost(cost, cost.length - 1), minCost(cost, cost.length - 2))); // 15