Tổng hợp câu hỏi phỏng vấn về dynamic programming: state transition, knapsack, subsequence và Java template

GuideKhoảng 2952 từKhoảng 10 phút

Dynamic programming khó không phải vì code luôn dài, mà vì chỉ cần state definition sai thì transition equation, initialization và thứ tự duyệt phía sau đều sai theo.

Trong phỏng vấn, đừng vội học thuộc template ngay từ đầu. Trước tiên hãy tự hỏi hai câu: bài toán này có thể tách thành các bài toán con không? Đáp án hiện tại có phụ thuộc vào các đáp án đã tính trước đó không? Nếu cả hai câu trả lời đều là có, hãy cân nhắc DP.

Trọng tâm phỏng vấn

Có thể nói rõ ý nghĩa của dp[i] hoặc dp[i][j].
Có thể viết được transition equation.
Có thể xử lý initialization và thứ tự duyệt.
Có thể xác định có nên nén space hay không.
Có thể phân biệt các dạng thường gặp: knapsack, subsequence và interval.

Khi nào nên cân nhắc dynamic programming?

Không phải cứ thấy bài hỏi “giá trị tối ưu” là áp dụng DP. Cách phán đoán đáng tin cậy hơn là kiểm tra hai điều kiện:

Bài toán có thể tách thành các bài toán cùng dạng với quy mô nhỏ hơn không.
Các bài toán con có bị tính lặp lại không.

Ví dụ, Fibonacci sequence, f(n) phụ thuộc vào f(n - 1) và f(n - 2), trong đó f(n - 2) sẽ bị tính lặp lại trong recursion. Lưu lại các kết quả trung gian này chính là DP.

Trong phỏng vấn, bạn có thể bắt đầu từ brute-force recursion, sau đó nói rõ phần nào bị tính lặp, cuối cùng chuyển recursion thành memoization search hoặc tabulation. Cách làm này dễ khiến interviewer tin rằng bạn thực sự hiểu, thay vì chỉ học thuộc mảng dp.

5 bước giải DP

Định nghĩa state: dp[i] rốt cuộc biểu thị điều gì.
Viết transition: state hiện tại được suy ra từ những state nào.
Thực hiện initialization: khi không có state trước đó thì đáp án là gì.
Xác định thứ tự duyệt: tính state nào trước, state nào sau.
Kiểm tra sample: dùng một input nhỏ để tính thử mảng.

Trong đó bước 1 quan trọng nhất. Một khi ý nghĩa của dp[i] mơ hồ, code phía sau sẽ chỉ là kết quả của việc thử-sai.

Một state definition tốt thường thỏa mãn:

Có thể bao quát đáp án mà đề bài hỏi.
Có thể suy ra từ state nhỏ hơn.
Số chiều nên ít nhất có thể, nhưng không được vì tiết kiệm space mà làm rối ý nghĩa.

Ví dụ DP một chiều

Bài toán Climbing Stairs:

int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int prev2 = 1;
    int prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Ý nghĩa state: có bao nhiêu cách đi đến bậc i. Transition equation: dp[i] = dp[i - 1] + dp[i - 2].

Bài này cũng có thể suy ra bằng recursion:

Bước cuối cùng để đến bậc i là đi 1 bước từ i-1, hoặc đi 2 bước từ i-2.

Vì dp[i] chỉ phụ thuộc vào hai state trước đó, có thể nén mảng thành hai biến. Điều kiện để nén space là xác nhận rằng về sau không cần dùng lại các state cũ.

Template 0-1 knapsack

Mỗi item chỉ được chọn một lần:

int knapsack01(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

Phải duyệt capacity theo thứ tự giảm dần để tránh sử dụng lặp lại cùng một item trong một lượt duyệt.

Duyệt theo thứ tự giảm dần là điểm thường được hỏi nhất trong 0-1 knapsack. Nếu duyệt capacity theo thứ tự tăng dần, khi tính dp[j] có thể dùng dp[j - weight] vừa được cập nhật trong vòng hiện tại, tương đương với việc chọn cùng một item nhiều lần. Khi đó bài toán đã trở thành unbounded knapsack.

Cách hỏi điển hình về 0-1 knapsack không nhất thiết gọi trực tiếp là knapsack. Ví dụ, bài “có thể chia thành hai subset có tổng bằng nhau hay không” có thể chuyển thành: có thể chọn một số phần tử từ array sao cho tổng của chúng bằng một nửa tổng các phần tử không.

Template unbounded knapsack

Mỗi item có thể được chọn nhiều lần:

int unboundedKnapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = weights[i]; j <= capacity; j++) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

Duyệt capacity theo thứ tự tăng dần để cho phép dùng lại item hiện tại.

Trong unbounded knapsack, việc duyệt capacity theo thứ tự tăng dần chính là để cho phép dùng lại item hiện tại. Ví dụ với Coin Change, mỗi loại coin có thể dùng nhiều lần; khi tính số tiền lớn hơn, có thể tiếp tục transition từ state đã được cập nhật bởi coin hiện tại.

Nếu đề hỏi “số combination” hay “số permutation” thì thứ tự duyệt cũng thay đổi:

Số combination: thường duyệt item trước, sau đó duyệt capacity.
Số permutation: thường duyệt capacity trước, sau đó duyệt item.

Phần này trong phỏng vấn có thể không bị hỏi quá sâu, nhưng rất quan trọng khi gặp các bài như Coin Change II.

Các dạng bài thường gặp

Dạng bài	Thiết kế state	Bài tiêu biểu
Climbing Stairs/House Robber	`dp[i]` biểu thị giá trị tối ưu của `i` vị trí đầu tiên	70, 198
Knapsack	`dp[j]` biểu thị giá trị tối ưu hoặc số phương án khi capacity bằng `j`	416, 518, 322
Subsequence	`dp[i]` hoặc `dp[i][j]` biểu thị đáp án kết thúc tại một vị trí hoặc của hai prefix	300, 1143
Palindrome	`dp[i][j]` biểu thị interval `[i, j]` có thỏa điều kiện hay không hoặc giá trị tối ưu	647, 516
Path	`dp[i][j]` biểu thị đáp án khi đi đến ô `(i, j)`	62, 64

Nên chọn memoization search hay tabulation?

Cả hai cách viết đều lưu đáp án của các bài toán con.

Cách viết	Đặc điểm	Trường hợp phù hợp
Memoization search	Từ target state đệ quy xuống, chỉ tính khi cần	State transition phức tạp, recursion tự nhiên hơn
Tabulation	Điền bảng từ state nhỏ đến state lớn	Thứ tự duyệt rõ ràng, thuận tiện nén space

Nếu ban đầu chưa nghĩ rõ thứ tự duyệt, bạn có thể viết memoization search trước. Sau khi quan hệ giữa các state rõ ràng, hãy chuyển thành tabulation. Nhiều tree DP và interval DP sẽ dễ viết đúng hơn khi dùng memoization search.

Cách trình bày khi viết tay trong phỏng vấn

Không nên bắt đầu trực tiếp từ code khi làm bài DP. Khi giải bằng tay trong phỏng vấn, bạn có thể nói rõ 4 điểm sau trước tiên:

Mảng dp có ý nghĩa gì, đáp án cuối cùng nằm ở vị trí nào.
State hiện tại phụ thuộc vào những state cũ nào, vì sao những state cũ đó đã được tính.
Vì sao initialization được viết như vậy, đặc biệt 0, 1 và infinity lần lượt biểu thị điều gì.
Vì sao thứ tự duyệt không sử dụng sớm các state chưa tính hoặc lặp lại các state không được phép dùng nhiều lần.

Nếu không nói rõ được 4 câu này thì code rất có thể được viết dựa vào trí nhớ; khi gặp biến thể sẽ dễ mất phương hướng.

Phân tích chi tiết bài tiêu biểu: Coin Change

322. Coin Change là một bài rất phù hợp cho phỏng vấn về unbounded knapsack. Đề bài cho các mệnh giá coin và target amount, hỏi cần ít nhất bao nhiêu coin để tạo thành target amount; mỗi coin có thể được dùng vô hạn lần.

State definition có thể được trình bày như sau:

dp[j] biểu thị số coin ít nhất cần để tạo thành amount j.

Initialization là điểm then chốt của bài này. dp[0] = 0 biểu thị tạo thành amount 0 không cần coin; các amount còn lại trước tiên được đặt thành một giá trị lớn chắc chắn không thể là đáp án, biểu thị tạm thời chưa thể đạt.

Code dùng Arrays.fill, cần import java.util.Arrays.

int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, max);
    dp[0] = 0;

    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }

    return dp[amount] == max ? -1 : dp[amount];
}

Vì sao phải duyệt capacity theo thứ tự tăng dần? Vì một coin có thể được dùng nhiều lần. Khi tính dp[j], dùng dp[j - coin]; nếu dp[j - coin] đã được coin hiện tại cập nhật trong vòng này thì có nghĩa là coin hiện tại có thể tiếp tục được dùng, đúng với unbounded knapsack.

Nếu đề biến thành “mỗi loại coin chỉ được dùng một lần” thì phải duyệt capacity theo thứ tự giảm dần. Hướng duyệt không phải vấn đề về format; nó dùng để kiểm soát việc một item có được tham gia nhiều lần vào transition hay không.

So sánh state definition

Trong các bài DP, vấn đề thường không phải là không viết được transition, mà là chọn sai ý nghĩa của state. Một số nhóm state dưới đây trông gần giống nhau nhưng cách viết hoàn toàn khác:

Dạng bài	Ý nghĩa state	Điểm cần chú ý khi transition
Longest Increasing Subsequence	`dp[i]` biểu thị độ dài LIS kết thúc tại `nums[i]`	Bắt buộc chọn `nums[i]`, tìm giá trị nhỏ hơn ở phía trước
House Robber	`dp[i]` biểu thị số tiền lớn nhất của `i` căn nhà đầu tiên	Trộm hoặc không trộm căn nhà thứ `i`
Longest Common Subsequence	`dp[i][j]` biểu thị độ dài LCS của hai prefix	So sánh ký tự cuối của hai prefix
Palindromic Substring	`dp[i][j]` biểu thị interval `[i, j]` có phải palindrome không	Phụ thuộc vào interval bên trong `[i + 1, j - 1]`

Trong phỏng vấn, bạn có thể chủ động nói một câu: dp[i] ở đây là “kết thúc tại i”, không phải “giá trị tối ưu trong i phần tử đầu tiên”. Câu này giúp tránh nhiều lỗi khi viết bài subsequence.

Minh họa quá trình và ví dụ biên

Lấy Climbing Stairs làm ví dụ, khi n = 5, state thay đổi như sau:

`i`	`dp[i - 2]`	`dp[i - 1]`	`dp[i]`
3	1	2	3
4	2	3	5
5	3	5	8

Bảng này không nhằm nhấn mạnh các con số, mà cho thấy state chỉ phụ thuộc vào hai vị trí trước đó nên có thể nén thành hai biến.

Với bài DP, nên kiểm tra các trường hợp biên sau:

Input	Điểm cần chú ý
`n = 0` hoặc array rỗng	Initialization đã bao quát chưa
Chỉ có 1 phần tử	Có truy cập vượt giới hạn `dp[1]` không
Không thể tạo thành target	Giá trị khởi tạo có thể biểu thị “không thể đạt” không
Tính số phương án	Initialization và thứ tự duyệt có đúng không

Cách viết dễ sai:

for (int j = weights[i]; j <= capacity; j++) {
    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]); // sai trong 0-1 knapsack
}

Trong 0-1 knapsack, phải duyệt capacity theo thứ tự giảm dần; nếu không, state vừa được cập nhật trong vòng hiện tại sẽ bị dùng lại, tương đương với việc chọn cùng một item nhiều lần.

Điểm dễ sai

Không được liên tục thay đổi ý nghĩa của dp.
Initialization không phải cứ điền 0 tùy ý, mà phải xem ý nghĩa của state.
Capacity của 0-1 knapsack duyệt theo thứ tự giảm dần, capacity của unbounded knapsack duyệt theo thứ tự tăng dần.
Initialization khi tính số phương án khác với khi tính giá trị tối ưu.
Với bài subsequence, thường phải phân biệt “kết thúc tại i” và “trong i phần tử đầu tiên”.

Tự kiểm tra với các câu hỏi thường gặp

Vì sao bước đầu tiên của DP nhất định phải là định nghĩa state?
Memoization search và tabulation khác nhau thế nào? Khi nào viết memoization trước sẽ chắc chắn hơn?
Vì sao capacity của 0-1 knapsack phải được duyệt theo thứ tự giảm dần?
Vì sao capacity của unbounded knapsack có thể được duyệt theo thứ tự tăng dần?
Khi dp[i] biểu thị “kết thúc tại i” và khi biểu thị “i phần tử đầu tiên”, transition khác nhau thế nào?
Khi tính số lần ít nhất, giá trị lớn nhất và số phương án, initialization lần lượt cần chú ý điều gì?

Bài tập đề xuất

Lời cuối

Nếu nội dung hữu ích với bạn, hãy tiện tay tặng JavaGuide một Star miễn phí để ủng hộ: GitHub | Gitee.

JavaGuide đã được duy trì gần bảy năm, tích lũy 6100+ commit, với sự chung tay hoàn thiện của 620+ contributor. Star, phản hồi và PR của bạn đều là động lực để dự án tiếp tục cập nhật.

Nếu bạn đang chuẩn bị phỏng vấn backend / phát triển ứng dụng AI, có thể tham khảo Knowledge Planet của tôi, bao gồm các project thực tế về backend và AI, tối ưu CV, hỏi đáp 1-1 và tài liệu về các trọng điểm thường gặp, đã được duy trì liên tục sáu năm.