What Is DP and When to Use It

Concepts: pyDPSignals, pyMemoVsTabulation

The canonical example is Fibonacci. fib(n) = fib(n-1) + fib(n-2). Without caching, fib(5) calls fib(3) twice, fib(2) three times, fib(1) five times. The call tree is exponential. With caching, each subproblem is solved exactly once. That is the overlapping subproblems property in action. Fibonacci also has optimal substructure: to know fib(n), you only need fib(n-1) and fib(n-2), not all previous values. Both properties present. DP is the right tool. The Two Signals in a Problem Statement In an interview, you will not see a problem labeled 'dynamic programming.' You have to recognize it. The first signal is optimization: 'minimum cost,' 'maximum profit,' 'fewest steps.' The second signal is counting or feasibility: 'how many ways,' 'is it possible,' 'find all combinations.' Both signals su