gen-define-dynamic-programming-and-give-one-short-worked-example-3d70

Define dynamic programming and give one short worked example.

# Dynamic Programming **Dynamic Programming (DP)** is an optimization technique that solves complex problems by: 1. Breaking them into overlapping subproblems 2. Solving each subproblem once and storing the result 3. Reusing stored solutions instead of recomputing them ## Short Example: Fibonacci Numbers **Problem:** Find the 5th Fibonacci number where F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1 **DP Solution (Bottom-up):** ``` Store results in a table: n: 0 1 2 3 4 5 F(n): 0 1 ? ? ? ? Build up: F(2) = F(1) + F(0) = 1 + 0 = 1 F(3) = F(2) + F(1) = 1 + 1 = 2 F(4) = F(3) + F(2) = 2 + 1 = 3 F(5) = F(4) + F(3) = 3 + 2 = 5 Answer: F(5) = 5 ``` **Why DP helps:** Without DP, computing F(5) recursively would recalculate F(3) multiple times. DP computes each value once, reducing time complexity from O(2ⁿ) to O(n).