Lesson 24 — Quy hoạch động 1 chiều

DP 1D: state là một chỉ số dp[i], transition từ vài ô liền trước. Ba module dưới cho bạn thấy tận mắt bảng dp[] được điền từng ô, Kadane reset/continue, và LIS dựng đường tăng dài nhất.

1. DP table filler

Chọn một bài DP 1D. Nhấn Chạy từng bước để xem mảng dp[] được điền từng ô, kèm công thức transition đang áp dụng.

dp[]
Chọn bài và nhấn Chạy.

House robber & Decode dùng nums số; Decode dùng chuỗi số (vd 226). Nhập sai sẽ tự chuyển về ví dụ mặc định của bài.

2. Kadane visualizer (reset vs continue)

Đi qua từng phần tử. Tại mỗi bước, cur hoặc nối tiếp (cur+x) hoặc reset (=x, khi cur đang âm). best chạy theo giá trị lớn nhất.

Thử: cho mảng có số âm lớn ở giữa — Kadane "reset" ngay khi tổng chạy âm: mang gánh nặng âm chỉ kéo tương lai xuống.

Nhấn Bước để bắt đầu Kadane.
cur = — , best = —

Ô vàng = đang xét. Ô xanh lá = thuộc đoạn tốt nhất tìm được tới giờ. Reset xảy ra khi cur < 0 trước khi cộng.

3. Longest Increasing Subsequence

Thuật toán O(n²): dp[i] = 1 + max{dp[j] : j<i, nums[j]<nums[i]}. Animate điền dp[] rồi tô đường tăng dài nhất.

dp[]
Nhấn Bước để điền dp[].

Mỗi điểm là một phần tử (cao = giá trị). Đường tím nối LIS dài nhất khi chạy xong.