Przejdź do treści
Biblioteka skilli
Programowanie · Nauka i wyjaśnianie

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.

Licencja
MIT
Ostatnia zmiana repozytorium
28.10.2026

Ocena i bezpieczeństwo

100/ 100Klasa: dobry
Format25 / 25
Frontmatter z nazwą i opisem, poprawna nazwa, opis do 1024 znaków, nazwa zgodna z folderem.
Odkrywalność25 / 25
Opis mówi, kiedy użyć skilla, ma sensowną długość i jest w 3. osobie.
Treść35 / 35
Co najmniej 150 słów i do 500 linii, nagłówki, listy kroków, przykłady albo kod.
Higiena15 / 15
Bez zaślepek typu TODO, bez ścieżek Windows, z licencją.
Ryzykobrak sygnałów w skanie
Pliki w paczce
1
Skrypty
0
Komentarze HTML
0
Adresy URL w SKILL.md
0
Przestarzałość

Brak sygnałów. Repozytorium zmienione 28.10.2026, bez odwołań do wycofanych modeli i API.

Licencja

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

  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
Sekcje z nagłówków SKILL.md, w oryginale · 50 linii, 383 słów
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.

Uwagi i zgłoszenia

Wiadomość trafi do Bartosza Sokolińskiego. Adres e-mail jest potrzebny tylko do odpowiedzi. Szczegóły w polityce prywatności.