Greedy, dynamic programming and backtracking — Data Structures & Algorithms

10. Greedy, dynamic programming and backtracking

Advanced★ Must knowLesson 10 of 10

Greedy — make the locally best choice each step; works when that provably leads to the global best (activity selection, coin change with standard coins, Dijkstra, Huffman coding).

Dynamic programming (DP) — the problem has overlapping subproblems and optimal substructure; store answers to subproblems instead of recomputing.

csharp

// Fibonacci: naive recursion O(2ⁿ) → DP O(n)
long Fib(int n)
{
    if (n < 2) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) (a, b) = (b, a + b);
    return b;
}

// Coin change: fewest coins to make an amount (bottom-up table)
int MinCoins(int[] coins, int amount)
{
    var dp = new int[amount + 1];
    Array.Fill(dp, int.MaxValue); dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        foreach (int c in coins)
            if (c <= x && dp[x - c] != int.MaxValue) dp[x] = Math.Min(dp[x], dp[x - c] + 1);
    return dp[amount] == int.MaxValue ? -1 : dp[amount];
}

Approach: define the state (dp[i] = answer for the first i items/amount i), the transition (how dp[i] uses smaller states), base cases, and the order of filling. Top-down = recursion + memo (Dictionary cache); bottom-up = table.

Backtracking — build candidates step by step and undo choices that can't lead to a solution (permutations, subsets, N-Queens, Sudoku):

csharp

List<List<int>> Subsets(int[] nums)
{
    var result = new List<List<int>>();
    void Go(int i, List<int> current)
    {
        if (i == nums.Length) { result.Add([.. current]); return; }
        Go(i + 1, current);                    // skip nums[i]
        current.Add(nums[i]); Go(i + 1, current); current.RemoveAt(current.Count - 1);   // take it, then undo
    }
    Go(0, []);
    return result;
}