public class NaiveFibonacci {

    /**
     * Вычисляет n-е число Фибоначчи наивной рекурсией.
     * 
     * @param n порядковый номер, начиная с 0 (F(0)=0, F(1)=1)
     * @return n-е число Фибоначчи
     * @throws IllegalArgumentException если n отрицательный
     */
    public static long fibonacci(int n) {
        // Базовые случаи, соответствующие математическому определению
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        // Рекурсивный шаг: F(n) = F(n-1) + F(n-2)
        // Ключевой момент: два вызова на каждом уровне
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1) = 1
│   │   │   └── fibonacci(0) = 0
│   │   ├── fibonacci(1) = 1
│   │   └── 1 + 1 = 2
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) = 1
│   │   └── fibonacci(0) = 0
│   └── 2 + 1 = 3
├── fibonacci(3)
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) = 1
│   │   └── fibonacci(0) = 0
│   ├── fibonacci(1) = 1
│   └── 1 + 1 = 2
└── 3 + 2 = 5

import java.util.HashMap;
import java.util.Map;

public class MemoizedFibonacci {

    // Кэш для хранения вычисленных значений. Map<аргумент, результат>
    // Используем long для n, т.к. int может переполниться при больших значениях
    private static final Map<Long, Long> memo = new HashMap<>();
    
    // Инициализация базовых случаев в кэше
    static {
        memo.put(0L, 0L);
        memo.put(1L, 1L);
    }
    
    /**
     * Потоко-НЕБЕЗОПАСНАЯ версия. Для многопоточности использовать ConcurrentHashMap.
     */
    public static long fibonacci(long n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
        
        // Проверка кэша: если значение уже вычислено, возвращаем мгновенно
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // Рекурсивный шаг с мемоизацией
        // Вычисляем только один раз, результат сохраняется в memo
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        
        // Сохраняем в кэш перед возвратом
        memo.put(n, result);
        
        return result;
    }
    
    /**
     * Метод для сброса кэша в тестах. В продакшене так делать не стоит.
     */
    public static void clearCache() {
        memo.clear();
        memo.put(0L, 0L);
        memo.put(1L, 1L);
    }
}

public class FibonacciService {
    private final Map<Long, Long> memo = new ConcurrentHashMap<>();
    
    public FibonacciService() {
        memo.put(0L, 0L);
        memo.put(1L, 1L);
    }
    
    public long fibonacci(long n) {
        // computeIfAbsent — атомарная операция, потокобезопасная
        return memo.computeIfAbsent(n, key -> fibonacci(key - 1) + fibonacci(key - 2));
    }
}

public static long fibonacciBottomUp(long n) {
    if (n < 0) throw new IllegalArgumentException();
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    long[] dp = new long[(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[(int)n];
}

public static long fibonacciOptimized(long n) {
    if (n < 0) throw new IllegalArgumentException();
    if (n == 0) return 0;
    
    long a = 0, b = 1;
    for (long i = 2; i <= n; i++) {
        long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

/**
 * Динамическое программирование для оптимального размещения.
 * 
 * Состояние: dp[i][w] = минимальное незаполненное пространство
 * после размещения первых i книг на полках общей ширины w.
 */
public class ShelfOptimizer {
    
    public static int optimize(List<Integer> bookThicknesses, int shelfWidth) {
        int n = bookThicknesses.size();
        int[][] dp = new int[n + 1][shelfWidth + 1];
        
        // Инициализация
        for (int w = 0; w <= shelfWidth; w++) {
            dp[0][w] = w; // Без книг осталось все свободное пространство
        }
        
        // Заполнение таблицы
        for (int i = 1; i <= n; i++) {
            int thickness = bookThicknesses.get(i - 1);
            for (int w = 0; w <= shelfWidth; w++) {
                if (thickness > w) {
                    // Книга не помещается — переносим предыдущее состояние
                    dp[i][w] = dp[i - 1][w];
                } else {
                    // Выбираем лучшее: либо не кладем книгу, либо кладем
                    dp[i][w] = Math.min(
                        dp[i - 1][w], // Не кладем
                        dp[i - 1][w - thickness] // Кладем, освобождаем оставшееся место
                    );
                }
            }
        }
        
        return dp[n][shelfWidth];
    }
}

/**
 * Определение длины кратчайшего пути от start до end.
 * dp[v] = минимальная длина пути от start до v.
 */
public static int shortestPathLength(Map<String, List<String>> graph, String start, String end) {
    Map<String, Integer> dp = new HashMap<>();
    dp.put(start, 0);
    
    // BFS + DP гибрид
    Queue<String> queue = new ArrayDeque<>();
    queue.add(start);
    
    while (!queue.isEmpty()) {
        String current = queue.poll();
        int currentDist = dp.get(current);
        
        if (current.equals(end)) {
            return currentDist;
        }
        
        for (String neighbor : graph.getOrDefault(current, List.of())) {
            if (!dp.containsKey(neighbor) || dp.get(neighbor) > currentDist + 1) {
                dp.put(neighbor, currentDist + 1);
                queue.add(neighbor);
            }
        }
    }
    
    return -1; // Путь не найден
}

Это пример DP, где состояние — это вершина графа.

import java.util.HashMap;
import java.util.Map;

public class Task300126 {
    private static Map<Integer, Integer> cache = new HashMap<>();

    public static void main(String[] args) {
        System.out.println(fib300126(5));
        System.out.println(fib300126(3));
        System.out.println(fib300126(5));
    }

    static int fib300126(int n) {
        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        int result;
        if (n <= 1) {
            result = n;
        } else {
            result = fib300126(n - 1) + fib300126(n - 2);
        }

        cache.put(n, result);
        return result;
    }
}

Книг в "Фантастике" = 
  книги в "Фантастике" + 
  книги в "Научной фантастике" + 
  книги в "Фэнтези"