dsa-dynamic-programming-2d-knapsack-lcs
/dsa-dynamic-programming-2d-knapsack-lcs
Rozwiązuje przejścia po siatce, plecak 0/1, odległość edycyjną i najdłuższy wspólny podciąg metodą programowania dynamicznego 2D.
- Autor
- nextboxis ↗
- Repozytorium
- library-skill-agents ↗
- Licencja
- MIT
- Ostatnia zmiana repozytorium
- 28.10.2026
Ocena i bezpieczeństwo
- Pliki w paczce
- 1
- Skrypty
- 0
- Komentarze HTML
- 0
- Adresy URL w SKILL.md
- 0
Brak sygnałów. Repozytorium zmienione 28.10.2026, bez odwołań do wycofanych modeli i API.
MIT, otwarta: można używać i zmieniać, z zachowaniem informacji o autorze.
Co robi i kiedy
Rozwiązuje przejścia po siatce, plecak 0/1, odległość edycyjną i najdłuższy wspólny podciąg metodą programowania dynamicznego 2D.
Oryginalny opis (EN)
Use this skill when solving 2D grid traversals, 0/1 knapsack, edit distance, and longest common subsequence problems.
Jak działa
- When to use
- Core principles
- Step-by-step workflow
- Specifics & examples
- Common mistakes & pitfalls
- Verification checklist
- Related skills
Podgląd SKILL.md
---
name: dsa-dynamic-programming-2d-knapsack-lcs
description: Use this skill when solving 2D grid traversals, 0/1 knapsack, edit distance, and longest common subsequence problems.
---
# DSA: 2D Dynamic Programming, Knapsack & LCS
## When to use
Use this skill during technical interviews when sub-problems depend on two changing parameters (e.g., item index and remaining weight, or string pointers `i` and `j`).
## Core principles
- **2D State Formulation**: Define `dp[i][j]` unambiguously (e.g., LCS: length of longest common subsequence of `s1[0..i]` and `s2[0..j]`).
- **Match vs Mismatch Transitions**: If characters match, `dp[i][j] = 1 + dp[i-1][j-1]`. If mismatch, take `max(dp[i-1][j], dp[i][j-1])`.
- **0/1 Knapsack Reverse Traversal**: When compressing 2D knapsack DP to 1D, traverse capacity in reverse from `W` down to `weight` to avoid using the same item twice.
- **Boundary Row & Column Invariants**: Always allocate `(m + 1) x (n + 1)` matrices so row 0 and column 0 serve as empty-string or zero-capacity base cases.
## Step-by-step workflow
1. Establish state parameters: length of string 1 (`m`) and string 2 (`n`), or items and capacity.
2. Allocate `(m+1) x (n+1)` grid initialized to base values.
3. Fill row 0 and column 0 with appropriate boundary conditions.
4. Iterate nested loops from 1 to `m` and 1 to `n`.
5. Apply state transitions based on character match or item inclusion.
6. Return bottom-right cell `dp[m][n]`.
## Specifics & examples
```python
# Longest Common Subsequence: O(M * N) Time, O(M * N) Space
def longest_common_subsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
```
## Common mistakes & pitfalls
- Creating 2D arrays via `[[0] * n] * m`, which duplicates row references in Python.
- Forgetting to offset indices when accessing strings (`text1[i-1]` vs `text1[i]`).
- In 0/1 Knapsack 1D compression, iterating forwards, which turns it into Unbounded Knapsack.
## Verification checklist
- [ ] 2D grid allocated using independent row comprehension.
- [ ] String indices properly offset by -1 against 1-indexed DP table.
- [ ] Time and space complexities stated clearly as O(M * N).
## Related skills
- dsa-dynamic-programming-1d-memoization-tabulation
- dsa-backtracking-subsets-permutations-n-queens
- dsa-time-space-complexity-big-o-analysis
- coding-interview-communication-thinking-out-loud
Wersje
W bazie nie ma innych skilli o nazwie dsa-dynamic-programming-2d-knapsack-lcs.
Migawka bazy z 13.11.2026 · wersja paczki 7c63d5b38982 (skrót SHA-256 całej paczki)
Pobrania w ostatnich 30 dniach: 0 · ranking
Zgłoś problem z tym skillem: szkodliwa treść, błędny opis albo prośba autora o usunięcie.
Podobne skille
- 100dynamic-programming
Pomaga rozwiązywać problemy optymalizacyjne programowaniem dynamicznym: memoizacja i tabulacja, klasyczne zadania jak plecak, LCS, LIS, edit distance i coin change, według Knutha. - 100dynamic-programming-interviewer
Prowadzi rozmowę kwalifikacyjną z programowania dynamicznego dla poziomu mid i senior: memoizacja i tabulacja, DP 1D i 2D, plecak, LCS, LIS i wydawanie reszty, z podpowiedziami i tabelami. - 100dsa-dynamic-programming-1d-memoization-tabulation
Rozwiązuje zadania optymalizacyjne i liczące przez podział na nakładające się podproblemy 1D, z memoizacją i tabelaryzacją. - 95knapsack-problems
Formułuje i rozwiązuje problemy plecakowe (0-1, ograniczone, wielokrotne, wielowymiarowe, kwadratowe) programowaniem dynamicznym, branch-and-bound, MIP, ograniczeniami zachłannymi i metaheurystykami. - 91knapsack-problems
Pomaga rozwiązywać problemy plecakowe: wybór elementów przy ograniczeniach i maksymalizację wartości przy ograniczonej pojemności, w wariantach 0/1, ograniczonym, nieograniczonym i wielowymiarowym. - 100dynamic-programming
Stosuje programowanie dynamiczne w zawodach MCM i ICM do wieloetapowych problemów decyzyjnych z optymalną podstrukturą, jak plecak, najkrótsza ścieżka, alokacja zasobów i wydawanie reszty.