Skip to content
Skills Library
Programming · Learning & explanation

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.

Licence
MIT
Last repository change
28.10.2026

Assessment and security

100/ 100Class: good
Format25 / 25
Frontmatter with name and description, valid name, description up to 1,024 characters, name matching the folder.
Discoverability25 / 25
Description explains when to use the skill, has a reasonable length and uses third person.
Content35 / 35
At least 150 words and at most 500 lines, headings, step lists, examples or code.
Hygiene15 / 15
No placeholders such as TODO, no Windows paths, with a licence.
Riskno signals detected in the scan
Files in this package
1
Scripts
0
HTML comments
0
URLs in SKILL.md
0
Deprecation

No signals detected. Repository changed on 28.10.2026, without references to retired models or APIs.

Licence

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

  1. When to use
  2. Core principles
  3. Step-by-step workflow
  4. Specifics & examples
  5. Common mistakes & pitfalls
  6. Verification checklist
  7. Related skills
Original SKILL.md headings · 48 lines, 345 words
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.

Feedback and reports

Your message goes to Bartosz Sokoliński. An email address is needed only for a reply. See the privacy policy.