Learnitweb

Fibonacci Numbers Coding pattern

1. Introduction

The Fibonacci sequence is a classic sequence where each number is the sum of the two preceding ones:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n >= 2

Example sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Problem Statement (Basic Coding Problem):

Given an integer n, compute F(n) – the n-th Fibonacci number.

Fibonacci problems are fundamental because they teach recursion, dynamic programming, and optimization.

2. When to Use Fibonacci Pattern

Use this pattern when:

  1. A problem involves sequential recurrence relations.
  2. Subproblems overlap and repeated computation occurs.
  3. Each element depends on one or more previous elements.
  4. Problems involve counting sequences, paths, or ways.

Problem Indicators:

  • “Count ways to climb stairs”
  • “Number of sequences or paths”
  • “Recursive dependencies with previous results”

3. Core Idea

At each step, the problem can be solved by choosing between a set of previous states:

F(n) = F(n-1) + F(n-2)

The key is overlapping subproblems, which makes dynamic programming or memoization optimal.

4. Standard Solutions

4.1 Naive Recursion

public int fibRecursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibRecursive(n-1) + fibRecursive(n-2);
}
  • Time Complexity: O(2^n)
  • Space Complexity: O(n) (recursion stack)

4.2 Top-Down DP (Memoization)

public int fibTopDown(int n) {
    int[] memo = new int[n+1];
    Arrays.fill(memo, -1);
    return helper(n, memo);
}

private int helper(int n, int[] memo) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];

    memo[n] = helper(n-1, memo) + helper(n-2, memo);
    return memo[n];
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

4.3 Bottom-Up DP (Tabulation)

public int fibBottomUp(int n) {
    if (n == 0) return 0;
    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];
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)

4.4 Space-Optimized DP

public int fibOptimized(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int prev1 = 0, prev2 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev1 = prev2;
        prev2 = curr;
    }
    return prev2;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

5. Fibonacci Pattern Variants

Many problems can be reduced to Fibonacci-like recurrences.

5.1 Climbing Stairs Problem

Problem:

Given n stairs, count how many distinct ways to climb to the top if you can take 1 or 2 steps at a time.

Observation:

ways(n) = ways(n-1) + ways(n-2)

Java Solution:

public int climbStairs(int n) {
    if (n <= 1) return 1;
    int oneStep = 1, twoStep = 1;
    for (int i = 2; i <= n; i++) {
        int curr = oneStep + twoStep;
        twoStep = oneStep;
        oneStep = curr;
    }
    return oneStep;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

5.2 Tiling Problems (2×n Board)

Problem:

Count ways to tile a 2×n board using 1×2 dominoes.

Observation:

  • Place a vertical domino → reduces to 2×(n-1)
  • Place two horizontal dominoes → reduces to 2×(n-2)
ways(n) = ways(n-1) + ways(n-2)

Java Solution:

public int tileBoard(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;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

5.3 Decode Ways (Dynamic Programming)

Problem:

Given a string of digits, count the number of ways to decode it where ‘A’ → 1, ‘B’ → 2, …, ‘Z’ → 26.

Observation:

  • If the last digit forms a valid single number → add ways(n-1)
  • If the last two digits form a number ≤26 → add ways(n-2)

Java Solution:

public int numDecodings(String s) {
    if (s == null || s.length() == 0) return 0;
    int n = s.length();
    int prev2 = 1, prev1 = s.charAt(0) != '0' ? 1 : 0;

    for (int i = 1; i < n; i++) {
        int curr = 0;
        if (s.charAt(i) != '0') curr += prev1;
        int twoDigit = Integer.parseInt(s.substring(i-1, i+1));
        if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;

        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

5.4 House Robber Problem (1D)

Problem:

Given an array of integers representing money in houses, find the maximum amount you can rob without robbing two adjacent houses.

Observation:

  • Either rob current house → add value + max till house i-2
  • Or skip current house → max till house i-1
rob(i) = max(rob(i-1), rob(i-2) + nums[i])

Java Solution:

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int prev2 = 0, prev1 = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

6. Key Takeaways

  1. Fibonacci is a classic DP pattern with recurrence and overlapping subproblems.
  2. Base recurrence: F(n) = F(n-1) + F(n-2)
  3. Solutions: recursion, memoization, bottom-up DP, space optimization.
  4. Many problems reduce to Fibonacci-like patterns:
    • Climbing stairs → counting sequences
    • Tiling → placement problems
    • Decode ways → sequence count with constraints
    • House robber → optimal selection under adjacency constraint
  5. Recognize recurrence + base cases + overlapping subproblems → apply DP.