gen-in-3-4-sentences-explain-dynamic-programming-state-any-key-f-48fb

In 3-4 sentences, explain dynamic programming. State any key formula.

Dynamic programming is an optimization technique that solves complex problems by breaking them down into simpler overlapping subproblems and storing their solutions to avoid redundant calculations. It applies to problems exhibiting **optimal substructure** (optimal solution contains optimal solutions to subproblems) and **overlapping subproblems** (same subproblems are solved multiple times). The key principle is captured by the **Bellman equation**: $$V(s) = \max_{a} \left[R(s,a) + \gamma \sum_{s'} P(s'|s,a)V(s')\right]$$ where $V(s)$ is the optimal value at state $s$, combining immediate reward $R(s,a)$ with discounted future value, though simpler forms like $dp[i] = f(dp[i-1], dp[i-2], ...)$ are common in algorithmic problems.