1. Max Sum 1D
5
arr[i] 1 3 2 -10 5
dp[i] 1 4 6 -4 5
O(N)

dp[i] = totalan maksimal subsegment yg ujung kanannya indeks i
dp[i] = max(dp[i - 1] + arr[i], arr[i])

2. Prefix Sum
dp[i] = total semua bilangan dari indeks 0 - indeks i
arr[i] 1 3 2 -10 5
dp[i] 1 4 6 -4 1
dp[j] - dp[i - 1]

3. Max Sum 2D
O((N^2).M)
1 2 3
4 5 6
7 8 9

1 2 3
5 7 9
12 15 18



-5 10 10
4 -5 -5
6 -5 1

-5 10 10
-5 10 20

- Prefix Sum setiap kolom
- Algoritma Max Sum 1D

4. LIS
O(N^2)
dp[i] = subsequence terpanjang jika i menjadi ujung kanan sequencenya
dp[i] = (1 <= j < i) max(dp[j], arr[j] < arr[i]) + 1
3 7 4 5
1 2 2 3

5. Coin Change
dp[i] = koin minimal penukaran sebesar i
dp[i] = 1 <= j <= n, min(dp[i - coin[j]]) + 1. i >= coin[j]
dp[0] = 0

6. Knapsack 0-1
O(NM)
N = banyak barang
M = bobot tas
dp[i][j] = nilai maksimal jika barangnya ada sebanyak i (1 - i) bobot yang tersisa sebesar j
dp[i][j] = max(dp[i - 1][j - W[i]] + V[i], dp[i - 1][j]), j >= W[i]
dp[1][0] = 0;
dp[1][j] = V[1] -> j >= W[1]

7. MCM (Matrix Chain Multiplication)
dp[i][i] = 0
dp[i][j] = proses minimal utk mngalikan matriks ke - i sampai matriks ke - j
dp[i][j] = i <= k < j, min(dp[i][k] + dp[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1])

N buah matrix
N + 1 bilangan
3
1 2 3 4
1x2
2x3
3x4
axb
bxc
axbxc