Fibonacci Number (LeetCode 509)

Problem Statement

The Fibonacci sequence, denoted as F(n), starts with base values F(0) = 0 and F(1) = 1. For all integers n greater than 1, each term is the sum of the two preceding terms, following the formula F(n) = F(n-1) + F(n-2). Given an integer n, return the value of F(n).

Approach

We use an iterative dynamic programming approach to avoid redundant recursive calculations, runnning in O(n) time and O(1) space by only tracking the last two values of the sequence.

Implementation

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int first = 0, second = 1;
        for (int i = 2; i <= n; i++) {
            int current = first + second;
            first = second;
            second = current;
        }
        return second;
    }
}

Climbing Stairs (LeetCode 70)

Problem Statement

You need to climb n steps to reach the top of a staircase. Each move allows you to climb either 1 or 2 steps. Calculate the total number of distinct ways you can reach the top.

Approach

The number of ways to reach step n is the sum of ways to reach step n-1 (climb 1 step from there) and ways to reach step n-2 (climb 2 steps from there). We optimize space by only storing the previous two values instead of a full DP array.

Implementation

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        int prev1 = 1, prev2 = 1;
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

Minimum Cost Climbing Stairs (LeetCode 746)

Problem Statement

You are given an integer array cost where cost[i] is the fee required to climb up from the i-th step. After paying the fee, you can choose to climb 1 or 2 steps. You can start climbing from either step 0 or step 1. Return the minimum cost required to reach the top of the staircase, wich is the position after the last endexed step in the cost array.

Approach

We define the minimum cost to reach position i as the minimum of the cost to reach i-1 plus the fee at i-1, or the cost to reach i-2 plus the fee at i-2. The base cases are 0 cost for positions 0 and 1, as we can start there for free. We use constent space by tracking only the last two minimum cost values.

Implementation

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int totalSteps = cost.length;
        int prevTwoCost = 0, prevOneCost = 0;
        for (int currentPos = 2; currentPos <= totalSteps; currentPos++) {
            int currMinCost = Math.min(prevTwoCost + cost[currentPos - 2], prevOneCost + cost[currentPos - 1]);
            prevTwoCost = prevOneCost;
            prevOneCost = currMinCost;
        }
        return prevOneCost;
    }
}