Dynamic Programming. Paradigma algoritma berbasis subproblem optimal dan overlapping subproblems.

Setiap Chapter pada Section ini disusun bertahap: konsep dasar, implementasi C++, lalu latihan dan refleksi. Pastikan pembaca menyelesaikan Chapter sebelumnya karena topik saling berkaitan.

# Konsep Dynamic Programming

Definisi DP: optimal substructure dan overlapping subproblems.

Buka → # Memoization

DP top-down: simpan hasil sub-masalah di cache untuk menghindari recomputation.

Buka → # Tabulation

DP bottom-up: bangun tabel secara iteratif dari sub-masalah terkecil.

Buka → # Menentukan State DP

Cara merancang state DP: parameter yang dibutuhkan untuk mengambil keputusan.

Buka → # Menentukan Transisi DP

Cara menulis recurrence: pilihan apa yang tersedia di setiap state?

Buka → # Fibonacci dan DP Dasar

Progresi dari rekursi naif O(2^n) ke memo O(n) ke tabulation O(n) ke space-optimized O(1).

Buka → # Climbing Stairs

DP 1D paling klasik: jumlah cara naik tangga dengan langkah 1 atau 2.

Buka → # Coin Change

DP klasik: jumlah minimum koin atau jumlah cara untuk membentuk nilai tertentu.

Buka → # Knapsack

0/1 knapsack: maximasi nilai dengan batasan kapasitas. DP 2D dan optimasi ruang 1D.

Buka → # Longest Common Subsequence (LCS)

DP 2D klasik: subsequence terpanjang yang sama pada dua string, plus rekonstruksi.

Buka → # Longest Increasing Subsequence (LIS)

DP O(n²) dan optimasi O(n log n) dengan patience sorting.

Buka → # Edit Distance

DP 2D: jumlah minimum operasi insert, delete, replace untuk mengubah satu string ke string lain.

Buka → # Interval DP

DP pada interval [i, j] dengan mencoba semua titik potong k. Contoh: matrix chain multiplication.

Buka → # Tree DP

DP pada pohon: post-order traversal, dp[u] sebagai fungsi dp[v] anak-anaknya.

Buka → # Bitmask DP

DP dengan state bitmask untuk himpunan kecil (n ≤ 20). Contoh klasik: TSP.

Buka → # Optimasi Dynamic Programming

Teknik lanjutan: divide and conquer optimization, convex hull trick, monotone queue, Knuth optimization.

Buka →