Các dạng Dynamic Programming thường gặp khi phỏng vấn

Ba câu hỏi trước khi viết dp

DP phù hợp khi đáp án có thể ghép từ các bài toán con và cùng một bài toán con xuất hiện nhiều lần. Trước code, hãy trả lời: trạng thái đại diện điều gì; quyết định cuối tạo chuyển tiếp nào; các trạng thái phải được tính theo thứ tự nào. Nếu chưa nói được bằng câu, thêm chỉ số thường chỉ làm bảng lớn hơn.

Ví dụ “Trộm nhà”: không chọn hai nhà kề nhau, lợi nhuận có thể không dương. Với i nhà đầu, ta hoặc bỏ nhà i, hoặc lấy nó và buộc bỏ i-1. Đây là cấu trúc lựa chọn cuối rõ ràng. Không cần nhớ toàn bộ tập đã chọn; chỉ cần giá trị tốt nhất ở hai tình huống kế cận.

Chạy tay House Robber

Với 2,7,9,3,1, giữ hai giá trị: skip là tốt nhất khi không lấy phần tử hiện tại, take là phương án lấy nó. Trước mỗi x, new_take = old_skip + x; new_skip = max(old_skip, old_take). Các cặp sau từng bước là (0,2), (2,7), (7,11), (11,10), (11,12), nên đáp án 12.

Thứ tự gán quan trọng: new_take phải dùng old_skip, không dùng skip vừa cập nhật. Python dùng gán đồng thời; C++ và Java giữ biến tạm. Nếu cho phép không chọn nhà nào, mảng toàn âm trả 0. Nếu đề bắt buộc chọn ít nhất một, điều kiện gốc phải đổi.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

long long rob(const vector<long long>& a) {
    long long skip = 0, take = 0;
    for (long long x : a) {
        long long next_take = skip + x;
        skip = max(skip, take);
        take = next_take;
    }
    return max(skip, take);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) {
        cout << rob({2, 7, 9, 3, 1}) << '\n';
        return 0;
    }
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    cout << rob(a) << '\n';
    return 0;
}

import sys


def rob(a: list[int]) -> int:
    skip = take = 0
    for x in a:
        skip, take = max(skip, take), skip + x
    return max(skip, take)


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    a = data[1:] if data else [2, 7, 9, 3, 1]
    print(rob(a))


if __name__ == "__main__":
    main()

import java.util.*;

public class Main {
    static long rob(long[] a) {
        long skip = 0, take = 0;
        for (long x : a) {
            long nextTake = skip + x;
            skip = Math.max(skip, take);
            take = nextTake;
        }
        return Math.max(skip, take);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long[] a = {2, 7, 9, 3, 1};
        if (sc.hasNextInt()) {
            int n = sc.nextInt();
            a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextLong();
            }
        }
        System.out.println(rob(a));
    }
}

Dạng 1: DP tuyến tính

Climbing Stairs, House Robber, giải mã xâu và tách từ thường có trạng thái theo tiền tố. Tín hiệu là quyết định ở vị trí i chỉ phụ thuộc vài vị trí trước. Hãy hỏi cần biết bao nhiêu quá khứ. Nếu chỉ hai trạng thái, có thể nén bộ nhớ sau khi công thức đã đúng.

Sai lầm phổ biến là không định nghĩa i: dp[i] dùng i phần tử đầu hay kết thúc đúng tại i? Hai nghĩa tạo điều kiện gốc khác nhau. Viết câu ngay trên giấy. Với bài đếm, còn phải xác định modulo và trường hợp tiền tố rỗng.

Dạng 2: cái túi và tổng mục tiêu

Trạng thái thường là dp[s]: có thể đạt tổng s, số cách đạt s hoặc giá trị tốt nhất với sức chứa s. Điểm dễ sai nhất là hướng vòng lặp. Mỗi vật dùng tối đa một lần thì duyệt sức chứa giảm để không tái dùng nó trong cùng lượt. Vật dùng vô hạn thường duyệt tăng.

“Số cách” và “có tồn tại” không hoán đổi được. Với số cách, thứ tự vòng vật–tổng còn quyết định đếm tổ hợp hay hoán vị. Hãy chạy tay hai đồng xu nhỏ trước khi tin công thức.

Dạng 3: lưới

Đếm đường đi, tổng nhỏ nhất và hình vuông lớn nhất dùng trạng thái theo ô. Cần xác định chuyển động hợp lệ và chướng ngại. Thứ tự hàng–cột phải bảo đảm các ô nguồn đã có. Có thể nén một hàng nếu chuyển tiếp chỉ nhìn hàng hiện tại và trước, nhưng cập nhật trái sang phải hay phải sang trái tùy phụ thuộc.

Nếu có thể đi bốn hướng, DP quét một lần thường không đúng vì phụ thuộc tạo chu trình; hãy nghĩ BFS, Dijkstra hoặc trạng thái lớn hơn. Đây là ví dụ quan trọng của câu “khi nào không dùng DP”.

Dạng 4: hai chuỗi

LCS, Edit Distance, wildcard và palindrome thường dùng dp[i][j] cho hai tiền tố. Khi ký tự cuối khớp, chuyển tiếp khác khi không khớp. Bảng O(nm) dễ dựng nhưng cần nói rõ hàng 0, cột 0. Tối ưu bộ nhớ chỉ hợp lý nếu không phải truy vết hoặc bạn có chiến lược khác để dựng đáp án.

Chạy tay trên chuỗi dài 2–3. Một bảng nhỏ lộ ngay lỗi lệch chỉ số: ký tự thứ i trong cách đếm một gốc nằm ở s[i-1]. Đừng cố tránh hàng rỗng nếu nó làm điều kiện biên rối hơn.

Dạng 5: đoạn và khoảng

Matrix Chain, Burst Balloons và palindrome interval dùng trạng thái trên [l,r]. Chuyển tiếp thử điểm chia hoặc phần tử cuối được xử lý. Thứ tự thường theo độ dài đoạn tăng dần. Nếu quét l tăng đơn giản, các đoạn con cần thiết có thể chưa sẵn sàng.

Số trạng thái O(n²), mỗi trạng thái thử O(n) điểm chia dẫn đến O(n³). Hãy nói con số này trước khi tối ưu; đôi khi ràng buộc n nhỏ chính là tín hiệu interval DP.

Dạng 6: cây và DAG

Trên cây, trạng thái gắn với nút và lựa chọn như lấy/không lấy. DFS gom kết quả con vì không có chu trình. Trên DAG, topo cung cấp thứ tự tính. Nếu đồ thị có chu trình, cần xử lý SCC hoặc mô hình khác; gọi mọi DFS có memo là DP không tự làm phụ thuộc hợp lệ.

Khi trạng thái có “cha được chọn hay không”, hãy thử viết hai giá trị cho mỗi nút. Tránh đưa toàn bộ tập tổ tiên vào state nếu quyết định chỉ phụ thuộc quan hệ cục bộ.

Từ đệ quy vét cạn đến bottom-up

Bắt đầu bằng hàm solve(state) và liệt kê lựa chọn. Nếu cây lời giải lặp state, thêm memo. Sau đó đếm số state và chi phí mỗi state để có độ phức tạp. Chuyển bottom-up khi cần tránh sâu ngăn xếp hoặc giảm overhead. Cả hai phải giữ cùng định nghĩa.

Một lỗi phỏng vấn thường gặp là nói O(n) vì có memo nhưng mỗi state lại duyệt O(n) lựa chọn. Công thức đúng là số trạng thái nhân chi phí chuyển tiếp, cộng chi phí tiền xử lý.

Bảng nhận dạng nhanh

Những lỗi cần tự bắt

• State thiếu thông tin nên hai lịch sử khác nhau bị gộp sai.
• State thừa thông tin làm số trạng thái bùng nổ.
• Điều kiện gốc không khớp “cho phép rỗng” hay “bắt buộc chọn”.
• Duyệt sức chứa sai hướng trong 0/1 knapsack.
• Nén bộ nhớ nhưng ghi đè giá trị vẫn cần cho cùng vòng.
• Trả đúng giá trị nhưng không lưu cha khi đề yêu cầu dựng phương án.

Một bài tập thiết kế state không cần code

Lấy ba đề và chỉ viết state, transition, base, order. Với cầu thang: dp[i] là số cách tới đúng bậc i. Với đổi tiền ít nhất: dp[s] là số đồng ít nhất tạo tổng s, trạng thái không đạt là vô cùng. Với LCS: dp[i][j] là độ dài tốt nhất của hai tiền tố. Bài tập này tách lỗi mô hình khỏi lỗi cú pháp và giúp bạn nhận ra khi đang thêm chỉ số không cần thiết.

Sau đó tự hỏi output cần giá trị hay phương án. Nếu cần dựng phương án, lưu lựa chọn cha hoặc tái dựng từ bảng; nén còn một hàng có thể làm mất dữ liệu. Quyết định bộ nhớ phải theo hợp đồng cuối, không theo thói quen “O(1) luôn tốt hơn”.

Luyện ngay trên Big-O Coding

Bắt đầu từ DP một chiều rồi mở rộng sang cái túi, lưới và chuỗi trong lộ trình Coding Interview 150.

Câu hỏi thường gặp

Nguồn tham khảo

• GeeksforGeeks: Dynamic Programming
• CP-Algorithms: Introduction to DP
• Wikipedia: Dynamic programming