Ghi chú dynamic programming: từ trạng thái đến truy vết

Ví dụ

Với bài toán balo 0/1, gọi \(dp[i][w]\) là giá trị tốt nhất khi xét \(i\) vật đầu tiên và sức chứa \(w\).

\[ dp[i][w] = \max(dp[i-1][w], dp[i-1][w-a_i] + v_i) \]

for (let i = 1; i <= n; i++) {
  for (let w = 0; w <= W; w++) {
    dp[i][w] = dp[i - 1][w];
  }
}