🔴 ADVANCED

Everything so far had one obvious way to solve it. This tier is about choice — problems where many valid paths exist and you need a strategy: try everything but remember what you've already solved (DP), grab the locally-best option and hope it's globally best too (Greedy), explore and back up on dead ends (Backtracking), or always know the most urgent item without re-sorting the whole pile (Heaps). These eight topics are also where technical interviews spend most of their time, for exactly that reason.

16. Dynamic Programming (DP)

🧸 ELI5: Imagine you're climbing a staircase and someone asks "how many ways can you climb 30 steps if you can take 1 or 2 steps at a time?" Instead of recalculating from scratch every time (which is super slow), you write the answer for small staircases on sticky notes (2 steps = 2 ways, 3 steps = 3 ways...) and reuse those notes to quickly build up the answer for 30 steps. Never solve the same sub-problem twice — remember it!

🌍 Real life: A cashier making change with the fewest coins possible remembers the best way to make smaller amounts and builds up. GPS apps remembering the best sub-routes to avoid recalculating the same road segment's cost repeatedly. Netflix computing "best next recommendation" using cached sub-results.

📝 Pseudocode (Fibonacci with memoization):

memo = {}
function fib(n):
    if n <= 1: return n
    if n in memo: return memo[n]     // check the sticky note first!
    memo[n] = fib(n-1) + fib(n-2)    // write a new sticky note
    return memo[n]

🐹 Go:

package main

import "fmt"

func fib(n int, memo map[int]int) int {
	if n <= 1 {
		return n
	}
	if val, found := memo[n]; found { // check the sticky note
		return val
	}
	result := fib(n-1, memo) + fib(n-2, memo)
	memo[n] = result // write the sticky note for next time
	return result
}

func main() {
	memo := make(map[int]int)
	fmt.Println(fib(30, memo)) // 832040 — instant, thanks to memoization
}

🇨 C (the "sticky notes" are a plain array here — have[n] marks whether memo[n] has been written yet, since a C array has no built-in "key not found" like a Go map does):

#include <stdio.h>

#define MEMO_SIZE 64
static long memo[MEMO_SIZE];
static int  have[MEMO_SIZE];

long fib(int n) {
    if (n <= 1) return n;
    if (have[n]) return memo[n];        // check the sticky note first!
    long result = fib(n - 1) + fib(n - 2);
    memo[n] = result;                    // write a new sticky note
    have[n] = 1;
    return result;
}

int main(void) {
    printf("%ld\n", fib(30)); // 832040 — instant, thanks to memoization
    return 0;
}

⏱️ Complexity: Without memoization, naive Fibonacci is O(2ⁿ) (extremely slow — it re-solves the same problem millions of times). With memoization: O(n) — each sub-problem solved exactly once.