Choosing the Right Algorithmic Approach

Every major algorithm paradigm — divide and conquer, greedy, dynamic programming, and backtracking — solves problems by breaking them into smaller pieces, but each relies on a different structural assumption about how those pieces relate. Choosing the right paradigm is really about diagnosing which assumption your problem actually satisfies. This topic gives a practical decision framework you can apply to an unfamiliar problem in the first few minutes of an interview or design discussion.

Before picking a paradigm, ask three questions about the problem. First, can the optimal answer be built from optimal answers to smaller subproblems (optimal substructure)? Second, do those subproblems overlap — does solving one small subproblem help solve multiple larger ones (overlapping subproblems)? Third, if you make the locally best choice at each step, can you prove it never needs to be undone (a greedy-choice property, often justified with an exchange argument or matroid structure)? The answers to these three questions almost fully determine which paradigm fits.

When subproblems overlap and the optimal solution is composed of optimal subsolutions, dynamic programming is the right tool because it avoids the exponential recomputation of plain recursion by caching. The classic signal is a recursive definition where the same (state) tuple appears as an argument multiple times across different call paths. Examples covered in this course include 0/1 knapsack (state: item index, remaining capacity), longest common subsequence (state: prefix lengths of both strings), coin change (state: remaining amount), longest increasing subsequence (state: index and/or last value), matrix chain multiplication (state: subarray of matrices), and edit distance (state: prefix lengths). Choose bottom-up tabulation when you need every subproblem and want to avoid recursion overhead; choose top-down memoization when only a sparse subset of the full state space is actually reached.

Greedy algorithms make one irrevocable locally-optimal choice at each step and never reconsider it, which only produces a globally optimal answer when the problem has a provable greedy-choice property — formally, many such problems have an underlying matroid structure where the locally best choice among independent options is always safe. Activity selection (always pick the activity that finishes earliest among remaining compatible ones) and Huffman coding (always merge the two lowest-frequency nodes) are proven correct this way; fractional knapsack works greedily because items are divisible, while 0/1 knapsack does not because they are not. When you are not sure a greedy strategy is safe, try to find a small counterexample first — if none exists after a genuine attempt, and you can sketch an exchange argument (swapping any non-greedy choice for the greedy one never makes things worse), greedy is likely correct and will be faster than DP.

When a problem asks for all valid arrangements, one arrangement satisfying complex constraints, or an existence check over a combinatorially large space with no reusable subproblem structure, backtracking is the right shape: build a partial solution incrementally, check constraints as early as possible, and abandon (backtrack from) any partial solution that cannot be completed. N-Queens, Sudoku solving, and generating permutations/combinations are the canonical examples. The key difference from DP is that backtracking states are typically not reused across branches — each path through the search tree explores a genuinely different partial assignment, so memoization would not help, but constraint propagation and early pruning make the search tractable in practice even though the worst case remains exponential.

Divide and conquer applies when a problem can be split into subproblems that are solved completely independently (no shared state, no overlap) and then combined. Merge sort splits the array in half, sorts each half independently, and merges; the closest-pair-of-points algorithm splits points spatially and combines results across the dividing strip; quickselect partitions around a pivot and recurses into only one side. The giveaway that distinguishes this from DP is independence: solving the left half of a merge sort never needs any information computed while solving the right half, so there is nothing to cache or share, and the recurrence (commonly solved with the Master Theorem) captures the total cost directly.