12. Recursion, memoisation and dynamic programming

// Naive Fibonacci is O(2^n); memoised is O(n)
static long FibMemo(int n, Dictionary<int, long>? memo = null)
{
    memo ??= new();
    if (n < 2) return n;
    if (memo.TryGetValue(n, out var v)) return v;
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}

// Climbing stairs (1 or 2 steps) — bottom-up DP, same recurrence as Fibonacci
static int Climb(int n) { int a = 1, b = 1; for (int i = 2; i <= n; i++) (a, b) = (b, a + b); return b; }

// Permutations of a string — backtracking
static void Permute(string prefix, string rest, List<string> output)
{
    if (rest.Length == 0) { output.Add(prefix); return; }
    for (int i = 0; i < rest.Length; i++)
        Permute(prefix + rest[i], rest[..i] + rest[(i + 1)..], output);
}