# Dynamic Programming

> Solve problems with overlapping subproblems and optimal substructure using memoization or tabulation. Use when finding minimum cost, counting ways, or computing longest/shortest subsequences.

- Skill: `knoopx/dynamic-programming` (Agent Skill)
- Install (CLI): `npx skillmds@latest add knoopx/dynamic-programming`
- Raw SKILL.md: https://api.skillmd.com/api/skills/knoopx/dynamic-programming/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: AI & ML
- Author: knoopx (https://skillmd.com/u/knoopx)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/knoopx/dynamic-programming

---


## When to use

Use dynamic programming when a problem has overlapping subproblems (same computation repeated) and optimal substructure (optimal solution built from optimal sub-solutions).

## Signs

"find minimum cost," "count the number of ways," "longest/shortest subsequence," "can you reach."

## Rules

- Define state (what changes between subproblems) and recurrence (how states relate)
- Top-down with @cache is easiest to write; bottom-up tabulation avoids recursion limits and is often faster
- ALWAYS check if you can reduce space by keeping only the previous row/state instead of the full table
- NEVER memoize without verifying overlapping subproblems exist

## Approach

1. Identify the state variables
2. Write the recurrence relation
3. Choose top-down (@cache) or bottom-up (tabulation)
4. Optimize space if possible

## Example

"Min coins for amount" → state = remaining amount. Recurrence: `dp(n) = 1 + min(dp(n - c) for c in coins)`. Use @cache for top-down; reduce to O(amount) space.