DP 1 chiều (One-dimensional DP)

Bạn sẽ học được gì

DP 1 chiều là sân tập đầu tiên: mỗi bài toán được mô tả bằng một bảng dp một chiều, trong đó dp[i] là lời giải cho "phần bài toán tới vị trí i". Hai việc quan trọng nhất bạn sẽ luyện ở đây: (1) định nghĩa trạng thái dp[i] nghĩa là gì, và (2) viết công thức truy hồi nối dp[i] với các ô trước. Ta đi qua ba bài kinh điển: leo cầu thang, House Robber (cướp nhà), và LIS.

1. Trực quan: mỗi ô `dp` trả lời một câu hỏi nhỏ

Hãy hình dung bạn đi dọc một dãy ô. Tới mỗi ô, bạn dừng lại tự hỏi một câu duy nhất và viết câu trả lời vào ô đó. Câu trả lời của ô sau dựa vào câu trả lời của vài ô trước. Đi hết dãy là xong.

Bí quyết của mọi bài DP 1 chiều gói trong hai câu:

Trạng thái: dp[i] = lời giải tối ưu khi xét tới phần tử thứ i. Truy hồi: dp[i] = (cách ghép từ dp[i-1], dp[i-2], ... theo luật của bài).

2. Bài 1 — Leo cầu thang

Có n bậc thang. Mỗi bước bạn bước 1 hoặc 2 bậc. Hỏi có bao nhiêu cách lên tới đỉnh?

Đặt dp[i] = số cách lên tới bậc i. Muốn đứng ở bậc i, bước cuối của bạn hoặc từ bậc i-1 (bước 1 bậc) hoặc từ bậc i-2 (bước 2 bậc). Vậy:

   dp[i] = dp[i-1] + dp[i-2]      (giong het Fibonacci!)

   bac i :  0   1   2   3   4   5
   dp    :  1   1   2   3   5   8
            ^   ^
            |   chi co 1 cach toi bac 1
            1 cach (dung yen) toi bac 0

🐞 Leo cầu thang: điền dp cho n=5Bước 1/6

1dp = [1, 1, 0, 0, 0, 0]
2for i in range(2, 6):
3  dp[i] = dp[i-1] + dp[i-2]
4so_cach = dp[5]

Biến tại bước này

dp	[1, 1, 0, 0, 0, 0]

👉 dp[0]=1 (đứng yên), dp[1]=1 (chỉ 1 cách).

3. Bài 2 — House Robber (cướp nhà)

Một dãy nhà thẳng hàng, nhà thứ i có nums[i] tiền. Luật: không được cướp hai nhà liền kề (báo động sẽ kêu). Hỏi số tiền tối đa lấy được?

Đặt dp[i] = tiền tối đa khi xét tới nhà i. Tại nhà i bạn có hai lựa chọn:

Bỏ qua nhà i: lấy như tới nhà trước → dp[i-1].
Cướp nhà i: cộng nums[i], nhưng phải bỏ nhà i-1 → nums[i] + dp[i-2].

Chọn cái nào lớn hơn:

   dp[i] = max( dp[i-1],  nums[i] + dp[i-2] )

   nha   :  2   7   9   3   1
   dp    :  2   7  11  11  12
                    ^       ^
                    9+2=11  1+11=12  (cuop nha 0,2,4)

Đang tải trình chạy code…

4. Bài 3 — Dãy con tăng dài nhất (LIS)

Cho dãy số, tìm độ dài dãy con tăng dần dài nhất (longest increasing subsequence). "Dãy con" nghĩa là bỏ bớt vài phần tử nhưng giữ nguyên thứ tự, không cần liền kề.

Đặt dp[i] = độ dài LIS kết thúc đúng tại phần tử i. Để mở rộng tới i, ta nhìn lại mọi j phía trước: nếu nums[j] < nums[i] thì có thể nối i vào sau dãy kết thúc ở j.

   Voi moi i: nhin moi j < i, neu nums[j] < nums[i] thi
   dp[i] = max(dp[i], dp[j] + 1)

   nums :  10   9   2   5   3   7  101  18
   dp   :   1   1   1   2   2   3    4   4
                        ^   ^   ^    ^
                        2<5 2<3 ...  LIS = 4  (2,3,7,101)

Lưu ý truy hồi này nhìn mọi j phía trước nên độ phức tạp là O(n^2) (có bản O(n log n) nâng cao).

Đang tải trình chạy code…

5. Phân tích chung

Bài	Trạng thái `dp[i]`	Truy hồi	Thời gian
Leo cầu thang	số cách tới bậc `i`	`dp[i-1] + dp[i-2]`	O(n)
House Robber	tiền tối đa tới nhà `i`	`max(dp[i-1], nums[i]+dp[i-2])`	O(n)
LIS	LIS kết thúc tại `i`	`max(dp[j]+1)` với `nums[j] < nums[i]`	O(n^2)

Bẫy thường gặp:

Định nghĩa dp[i] mơ hồ ("liên quan tới i") thay vì chính xác → truy hồi sai.
Quên trường hợp cơ sở (dp[0], dp[1]) hoặc khởi tạo dp sai giá trị (LIS phải khởi tạo 1, không phải 0).
Với LIS, đáp án là max(dp) chứ không phải dp[n-1] (dãy dài nhất có thể kết thúc ở giữa).

6. Mẫu nhận diện

Đi dọc một dãy, mỗi vị trí có vài lựa chọn chỉ phụ thuộc vài vị trí trước → DP 1 chiều.
"Số cách", "tối đa/tối thiểu khi đi từ trái sang phải", "không được chọn liền kề" → DP 1 chiều.
Cảm giác bài "giống Fibonacci nhưng có thêm điều kiện" → gần như chắc chắn là DP 1 chiều.

7. 🎮 Trò chơi: DP 1 chiều

🎮 DP 1 chiềuCâu 1/4· Điểm 0· 🔥 0

dp[i] = lời giải tới vị trí i, ghép từ các ô trước theo luật của bài.

Với LIS, dp[i] khởi tạo bằng bao nhiêu?

8. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Trong DP 1 chiều, "định nghĩa trạng thái" nghĩa là gì?

2. Bài leo cầu thang có công thức truy hồi giống bài nào?

3. Đáp án của bài LIS là gì sau khi điền xong bảng dp?

9. Hoàn thành

…

☑️ Tiếp theo: 3.4.3 — DP 2 chiều (LCS, edit distance, 0/1 knapsack với bảng hai chiều).

1. Trực quan: mỗi ô dp trả lời một câu hỏi nhỏ​

2. Bài 1 — Leo cầu thang​

3. Bài 2 — House Robber (cướp nhà)​

4. Bài 3 — Dãy con tăng dài nhất (LIS)​

5. Phân tích chung​

6. Mẫu nhận diện​

7. 🎮 Trò chơi: DP 1 chiều​

8. Quiz kiểm tra nhanh​

9. Hoàn thành​