dsa-dynamic-programming-1d-memoization-tabulation
/dsa-dynamic-programming-1d-memoization-tabulation
Use this skill when solving optimization, counting, and decision problems by breaking them into overlapping 1D sub-problems.
- Author
- nextboxis ↗
- Repository
- library-skill-agents ↗
- Licence
- MIT
- Last repository change
- 28.10.2026
Assessment and security
- Files in this package
- 1
- Scripts
- 0
- HTML comments
- 0
- URLs in SKILL.md
- 0
No signals detected. Repository changed on 28.10.2026, without references to retired models or APIs.
MIT, open: use and modify while retaining author attribution.
What it does and when to use it
Use this skill when solving optimization, counting, and decision problems by breaking them into overlapping 1D sub-problems.
Original author description
Use this skill when solving optimization, counting, and decision problems by breaking them into overlapping 1D sub-problems.
How it works
- When to use
- Core principles
- Step-by-step workflow
- Specifics & examples
- Common mistakes & pitfalls
- Verification checklist
- Related skills
SKILL.md preview
---
name: dsa-dynamic-programming-1d-memoization-tabulation
description: Use this skill when solving optimization, counting, and decision problems by breaking them into overlapping 1D sub-problems.
---
# DSA: 1D Dynamic Programming, Memoization & Tabulation
## When to use
Use this skill when tackling classic interview problems like Climbing Stairs, Coin Change, House Robber, Decode Ways, or Longest Increasing Subsequence.
## Core principles
- **Optimal Substructure**: The optimal solution to the problem can be constructed from optimal solutions of its sub-problems.
- **Overlapping Sub-problems**: Recursive decomposition encounters the same sub-problems repeatedly, allowing caching (memoization) or bottom-up calculation (tabulation).
- **State Definition Clarity**: Define precisely what `dp[i]` represents before writing code (e.g., 'minimum coins to make amount `i`').
- **Space Optimization Rolling Variables**: If `dp[i]` depends only on `dp[i-1]` and `dp[i-2]`, eliminate the O(N) array in favor of two variables for O(1) space.
## Step-by-step workflow
1. Define the recurrence relation and exact state meaning of `dp[i]`.
2. Identify base cases (e.g., `dp[0] = 0` or `dp[0] = 1`).
3. Choose approach: top-down with memoization (`@functools.lru_cache`) or bottom-up tabulation.
4. Fill table iteratively from smallest sub-problems to target `N`.
5. Apply space optimization if previous states allow rolling updates.
6. Trace a small test case (e.g., `amount = 5`) manually out loud.
## Specifics & examples
```python
# Coin Change (Fewest coins to make amount): O(amount * len(coins)) Time
def coin_change(coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
```
## Common mistakes & pitfalls
- Failing to initialize DP array with appropriate identity values (`inf` for min, `-inf` for max).
- Off-by-one errors in allocating `dp` table size (`amount` vs `amount + 1`).
- Struggling to communicate the state transition equation to the interviewer before coding.
## Verification checklist
- [ ] State definition `dp[i]` is explicitly stated to the interviewer.
- [ ] Handled impossible targets (returning -1).
- [ ] Analyzed space optimization from O(N) to O(1) when applicable.
## Related skills
- dsa-dynamic-programming-2d-knapsack-lcs
- dsa-greedy-algorithms-interval-scheduling
- dsa-time-space-complexity-big-o-analysis
- coding-interview-communication-thinking-out-loud
Versions
The database has no other skills named dsa-dynamic-programming-1d-memoization-tabulation.
Database snapshot: 13.11.2026 · package version 3aecb9dca3fe (SHA-256 digest of the entire package)
Downloads in the last 30 days: 0 · ranking
Report a problem with this skill: harmful content, incorrect descriptions or an author’s removal request.
Similar skills
- 80role-algorithms:dynamic-programming
Solves optimization problems using dynamic programming — top-down memoization, bottom-up tabulation, state space design, dimension reduction, bitmask DP, interval DP, tree DP (with rerooting), DP on DAGs, and convex hull trick / divide-and-conquer optimizations. Use when solving… - 100dynamic-programming
Use when solving optimization problems with overlapping subproblems and optimal substructure. Covers memoization (top-down) vs tabulation (bottom-up), classic DP problems (Knapsack, LCS, LIS, Edit Distance, Coin Change, Matrix Chain, Rod Cutting), and the DP framework. Based on… - 95dynamic-programming
When the user wants to design and implement dynamic programming for combinatorial optimization — state-space design, Bellman recursions, memoization vs tabulation, solution recovery, and labeling algorithms for resource-constrained shortest paths. Also use when the user mentions… - 100dsa-dynamic-programming-2d-knapsack-lcs
Use this skill when solving 2D grid traversals, 0/1 knapsack, edit distance, and longest common subsequence problems. - 100dsa-revise
Track spaced repetition revision for DSA problems on your machine. Use when a student asks "revision due", "what should I revise", "spaced repetition", "check due problems", "log revision", or wants to check which problems are due for review. - 100dsa-next
Find what to solve next based on target role and current progress. Use when a student asks "what should I solve next", "what problem should I do next", "next problem for my role", "recommend DSA problems", or asks for role-specific interview preparation.