Fibonacci Numbers (Dynamic Programming)

import java.util.*;
public class Fibonacci {
    // Approach 1: Naive recursion (SLOW - O(2^n))
    public static int fibRecursive(int n) {
        if (n <= 1) return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }
    // Approach 2: Memoization (Top-down DP)
    public static int fibMemo(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        return fibMemoHelper(n, memo);
    }
    private static int fibMemoHelper(int n, Map<Integer, Integer> memo) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int result = fibMemoHelper(n - 1, memo) + fibMemoHelper(n - 2, memo);
        memo.put(n, result);
        return result;
    }
    // Approach 3: Tabulation (Bottom-up DP)
    public static int fibTabulation(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    // Approach 4: Space optimized (Best!)
    public static int fibOptimized(int n) {
        if (n <= 1) return n;
        int prev2 = 0;
        int prev1 = 1;
        int current = 0;
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fib(" + n + ") recursive: " + fibRecursive(n));
        System.out.println("Fib(" + n + ") memo: " + fibMemo(n));
        System.out.println("Fib(" + n + ") tabulation: " + fibTabulation(n));
        System.out.println("Fib(" + n + ") optimized: " + fibOptimized(n));
        // All output: 55
    }
}

public class ClimbingStairs {
    // This is exactly Fibonacci!
    // To reach step n, you came from step n-1 or n-2
    // ways(n) = ways(n-1) + ways(n-2)
    public static int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1;  // ways to reach step 1
        int prev1 = 2;  // ways to reach step 2
        int current = 0;
        for (int i = 3; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
    // With k steps allowed (more general)
    public static int climbStairsK(int n, int k) {
        int[] dp = new int[n + 1];
        dp[0] = 1;  // One way to stay at ground
        for (int i = 1; i <= n; i++) {
            // Sum all possible previous steps (1 to k steps back)
            for (int step = 1; step <= k && step <= i; step++) {
                dp[i] += dp[i - step];
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        int n = 5;
        System.out.println("Ways to climb " + n + " stairs: " + climbStairs(n));
        // Output: 8
        // [1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1]
        System.out.println("Ways with 3 steps allowed: " + climbStairsK(n, 3));
        // Output: 13
    }
}

public class HouseRobber {
    // At each house: rob it (skip previous) or skip it (keep previous max)
    // dp[i] = max(nums[i] + dp[i-2], dp[i-1])
    public static int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int prev2 = 0;
        int prev1 = nums[0];
        int current = 0;
        for (int i = 1; i < nums.length; i++) {
            // Rob current house + max from 2 houses back
            // OR skip current, keep previous max
            current = Math.max(nums[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
    // House Robber II: Houses in a circle (first and last are adjacent)
    public static int robCircular(int[] nums) {
        if (nums.length == 1) return nums[0];
        // Case 1: Rob houses 0 to n-2 (exclude last)
        int max1 = robRange(nums, 0, nums.length - 2);
        // Case 2: Rob houses 1 to n-1 (exclude first)
        int max2 = robRange(nums, 1, nums.length - 1);
        return Math.max(max1, max2);
    }
    private static int robRange(int[] nums, int start, int end) {
        int prev2 = 0;
        int prev1 = 0;
        int current = 0;
        for (int i = start; i <= end; i++) {
            current = Math.max(nums[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
    public static void main(String[] args) {
        int[] houses = {2, 7, 9, 3, 1};
        System.out.println("Max money (linear): " + rob(houses));
        // Output: 12 (rob houses 0, 2, 4: 2+9+1)
        int[] circularHouses = {2, 3, 2};
        System.out.println("Max money (circular): " + robCircular(circularHouses));
        // Output: 3 (can't rob both 0 and 2 since they're adjacent in circle)
    }
}