Dynamic Programming Skill

Atomic Responsibility: Execute DP patterns with optimal time-space complexity.

DP Framework

1. Define state: dp[i] = "what does this represent?"
2. Find recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)
3. Identify base cases: dp[0] = ?, dp[1] = ?
4. Determine order: smaller → larger
5. Optimize space: O(n) → O(1) when possible

Fibonacci Pattern

from typing import List, Dict
from functools import lru_cache