Quy hoạch động: Mô hình tư duy dễ nhớ và dùng được lâu dài

Quy hoạch động thường được dạy như một danh mục bài mẫu: Fibonacci, knapsack, dãy con chung dài nhất, đổi tiền. Cách học ấy biến mỗi đề mới thành một bài kiểm tra trí nhớ. Chỉ cần input không giống ví dụ quen thuộc, kỹ thuật tưởng như không còn chỗ bám.

Một mô hình tư duy tốt hơn lại khá gọn: quy hoạch động là quá trình tính một đồ thị có hướng không chu trình gồm các bài toán con được tái sử dụng. State đặt tên cho một đỉnh. Transition mô tả các dependency đi ra từ đỉnh đó. Base case là những đỉnh đã biết đáp án. Memoization và tabulation chỉ là hai lịch tính khác nhau cho cùng một đồ thị.

Góc nhìn này biến DP từ tập hợp mẹo thành một quy trình thiết kế. Nó còn giải thích những chi tiết mà template thường che khuất: vì sao state cần biến này mà không cần biến kia, vì sao hướng lặp quan trọng, khi nào greedy không an toàn, làm sao dựng lại lời giải thật sự, và độ phức tạp thời gian lẫn bộ nhớ đến từ đâu.

Nhìn thấy DAG ẩn sau lời gọi đệ quy #

Giả sử ta cần tìm đường có tổng chi phí nhỏ nhất từ góc trên trái đến góc dưới phải của một ma trận chữ nhật. Từ mỗi ô chỉ được đi sang phải hoặc đi xuống. Một lời giải đệ quy ngây thơ sẽ tách thành hai nhánh ở hầu hết các ô và giải đi giải lại cùng những đoạn đường phía sau.

Gọi $F(r,c)$ là chi phí nhỏ nhất của đường đi bắt đầu ở ô $(r,c)$ và kết thúc tại đích, tính cả hai đầu mút. Ta có truy hồi

Ô đích là base case:

Vị trí ngoài ma trận có chi phí $\infty$, vì thế không bao giờ thắng phép lấy minimum. Điều quan trọng không chỉ là công thức. Một lời gọi như $F(1,1)$ có thể được đi tới qua nhiều đường khác nhau, nhưng đáp án của nó chỉ phụ thuộc vào tọa độ. Những lời gọi lặp lại ấy thực ra là một đỉnh dùng chung trong DAG.

Đồ thị không có chu trình vì mỗi bước luôn tăng chỉ số hàng hoặc cột. Một thứ tự tính hợp lệ phải hoàn tất mọi dependency trước state đang dùng chúng. Đệ quy top-down tự khám phá thứ tự đó theo nhu cầu; các vòng lặp bottom-up mô tả thứ tự một cách tường minh.

DP khác divide-and-conquer ở chỗ các nhánh hội tụ về cùng state. Nếu có $S$ state đi tới được và mỗi state xét tối đa $T$ công việc chuyển tiếp, cận quen thuộc là

Thiết kế state trước khi viết code #

Phần khó nhất của DP thường là quyết định một state mang ý nghĩa gì. State tốt là bản tóm tắt đầy đủ nhưng tối thiểu về quá khứ: đủ đầy để đáp án tương lai chỉ phụ thuộc vào state, nhưng đủ gọn để những lịch sử tương đương được nhập lại thành một.

Hãy dùng câu này như công cụ thiết kế: dp(state) trả về …. Nếu câu chưa rõ nghĩa, implementation cũng sẽ mơ hồ. Với bài toán ma trận, solve(row, col) trả về chi phí còn lại nhỏ nhất từ (row, col), có tính chi phí ô hiện tại. Cách diễn đạt đó quyết định transition và tránh lỗi cộng ô hiện tại hai lần.

Nếu chuyển động còn phụ thuộc vào số lần được phép phá chướng ngại vật thì sao? Chỉ có tọa độ không còn đầy đủ. Hai lần tới (r, c) với hai ngân sách còn lại khác nhau mở ra những tương lai khác nhau, nên state phải trở thành (r, c, removalsLeft). Ngược lại, lưu toàn bộ prefix của đường đi tuy đầy đủ nhưng không tối thiểu: rất nhiều prefix có cùng vị trí và ngân sách sẽ không thể nhập lại.

Trình tự thiết kế state thực dụng gồm:

1. Xác định biên quyết định: lựa chọn tiếp theo được thực hiện ở đâu?
2. Liệt kê thông tin quá khứ có thể thay đổi lựa chọn hợp lệ hoặc chi phí tương lai.
3. Bỏ thông tin có thể suy ra từ các biến state khác.
4. Viết câu mô tả giá trị trả về, bao gồm việc có tính hai đầu mút hay không.
5. Thử tạo hai lịch sử có cùng state đề xuất nhưng tương lai khác nhau. Nếu làm được, state còn thiếu.

State (index, remainingCapacity) cho 0/1 knapsack tạo xấp xỉ $nW$ đỉnh. Thêm dữ liệu thừa làm phình đồ thị; bỏ remainingCapacity lại nhập chung các lịch sử không tương thích. Vì thế, hãy đặc tả ý nghĩa, transition, base case và invalid case trước khi chọn top-down hay bottom-up.

Tính top-down bằng memoization #

Memoization giữ nguyên hình dạng của định nghĩa đệ quy. Đây thường là implementation đầu tiên tốt nhất vì control flow gần với recurrence, state không đi tới được sẽ không bị tính, và ta dễ kiểm tra tính đúng đắn cục bộ hơn.

type Position = Readonly<{ row: number; col: number }>;

type PathResult = Readonly<{
  cost: number;
  path: ReadonlyArray<Position>;
}>;

export function minPathMemo(grid: ReadonlyArray<ReadonlyArray<number>>): PathResult | null {
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;
  if (rows === 0 || cols === 0 || grid.some((row) => row.length !== cols)) {
    return null;
  }

  const memo: Array<Array<number | undefined>> = Array.from(
    { length: rows },
    () => Array<number | undefined>(cols),
  );

  function solve(row: number, col: number): number {
    if (row >= rows || col >= cols) return Number.POSITIVE_INFINITY;
    if (row === rows - 1 && col === cols - 1) return grid[row]![col]!;

    const cached = memo[row]![col];
    if (cached !== undefined) return cached;

    const bestSuffix = Math.min(solve(row + 1, col), solve(row, col + 1));
    const result = grid[row]![col]! + bestSuffix;
    memo[row]![col] = result;
    return result;
  }

  const cost = solve(0, 0);
  const path: Position[] = [];
  let row = 0;
  let col = 0;

  while (true) {
    path.push({ row, col });
    if (row === rows - 1 && col === cols - 1) break;

    const down = solve(row + 1, col);
    const right = solve(row, col + 1);
    if (right <= down) col += 1;
    else row += 1;
  }

  return { cost, path };
}

Cache phải phân biệt “chưa tính” với đáp án bằng không, nên code dùng undefined thay vì kiểm tra truthy. Infinity mang ý nghĩa khác: transition không hợp lệ. Reconstruction đọc lại hai child đã cache và đi theo suffix tối ưu; quy tắc hòa right <= down chỉ giúp output ổn định. Ta cũng có thể lưu parent hoặc next-move khi tính state.

Có nhiều nhất $RC$ state đi tới được, mỗi state làm lượng công việc hằng số, nên thời gian là $O(RC)$ và bộ nhớ memo là $O(RC)$. Recursion stack có thể sâu tới $O(R+C)$. Rủi ro tràn stack là lý do thực tế để chọn tabulation cho đồ thị state rất sâu, dù hai cách có cùng big-O.

Tính bottom-up bằng tabulation #

Tabulation chọn topological order một cách tường minh. Vì dp[row][col] phụ thuộc vào ô phía dưới và ô bên phải, cả hàng lẫn cột phải được duyệt ngược. Đổi hướng vòng lặp mà không đổi ý nghĩa state sẽ đọc giá trị trước khi chúng tồn tại.

type Move = 'right' | 'down' | 'done';

export function minPathTable(grid: ReadonlyArray<ReadonlyArray<number>>): PathResult | null {
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;
  if (rows === 0 || cols === 0 || grid.some((row) => row.length !== cols)) {
    return null;
  }

  const dp = Array.from({ length: rows }, () => Array<number>(cols).fill(0));
  const next = Array.from({ length: rows }, () => Array<Move>(cols).fill('done'));

  for (let row = rows - 1; row >= 0; row -= 1) {
    for (let col = cols - 1; col >= 0; col -= 1) {
      if (row === rows - 1 && col === cols - 1) {
        dp[row]![col] = grid[row]![col]!;
        continue;
      }

      const down = row + 1 < rows ? dp[row + 1]![col]! : Number.POSITIVE_INFINITY;
      const right = col + 1 < cols ? dp[row]![col + 1]! : Number.POSITIVE_INFINITY;

      if (right <= down) {
        dp[row]![col] = grid[row]![col]! + right;
        next[row]![col] = 'right';
      } else {
        dp[row]![col] = grid[row]![col]! + down;
        next[row]![col] = 'down';
      }
    }
  }

  const path: Position[] = [];
  let row = 0;
  let col = 0;
  while (true) {
    path.push({ row, col });
    const move = next[row]![col]!;
    if (move === 'done') break;
    if (move === 'right') col += 1;
    else row += 1;
  }

  return { cost: dp[0]![0]!, path };
}

Value table và hàm memoized đại diện cho cùng đồ thị, nhưng khác cách vận hành:

Nếu chỉ cần chi phí, table có thể nén còn một hàng, tức $O(C)$. Nhưng dựng toàn bộ đường đi vẫn cần matrix next cỡ $O(RC)$. Tối ưu bộ nhớ vì thế phải dựa trên output: witness cần thông tin mà một đáp án vô hướng không cần.

Chẩn đoán lỗi từ chính mô hình #

Phần lớn bug DP là lỗi đặc tả đội lốt lỗi index. Mô hình state graph cho ta cách tìm chúng có hệ thống.

State chưa đầy đủ nhập chung những tình huống có tương lai khác nhau. Bài giao dịch cổ phiếu giới hạn số lượt không thể chỉ lưu ngày; state còn phải biết số lượt còn lại.

State phình to giữ lịch sử không liên quan. Đưa toàn bộ item đã chọn vào cache knapsack ngăn các bài toán con tương đương nhập lại. Chỉ cache giá trị theo state tối thiểu; lưu lựa chọn riêng để reconstruction.

Ý nghĩa không nhất quán gây lỗi lệch một đơn vị. “Tốt nhất tính đến i” và “tốt nhất bắt đầu từ i” cần transition cùng thứ tự tính ngược nhau. Hãy viết nghĩa của state trước vòng lặp.

Base case thiếu thường ẩn ở input rỗng và đường biên. Hãy test instance nhỏ nhất, trường hợp chỉ có một bước và trường hợp mọi transition đều invalid. Base case phải là đáp án toán học hoàn chỉnh, không chỉ dừng đệ quy.

Sai hướng lặp vi phạm dependency: child phải được tính trước parent. Trong 0/1 knapsack, cập nhật capacity từ cao xuống thấp ngăn item hiện tại bị dùng lại; chiều ngược lại biến bài toán thành unbounded knapsack.

Dùng greedy không chứng minh loại nhánh trước khi biết chi phí tương lai. Greedy chỉ an toàn khi exchange argument hoặc chứng minh tương đương bảo đảm lựa chọn cục bộ thuộc một nghiệm tối ưu.

Khi debug, hãy so memoization và tabulation trên input ngẫu nhiên nhỏ rồi đối chiếu với brute force. Brute force là oracle tốt cho ma trận ba hoặc bốn ô mỗi chiều. Nếu kết quả lệch, hãy in dependency chứ không chỉ array cuối.

Luyện tập vòng thiết kế và đúc kết #

Kỹ năng DP tiến bộ nhanh hơn nhờ biến đổi có kiểm soát thay vì sưu tầm lời giải. Với mỗi bài luyện tập, nên dành phần lớn thời gian cho một bản đặc tả ngắn trước khi code:

1. Viết các lựa chọn brute-force để lộ ra cây recurrence.
2. Đặt tên state và hoàn thành câu “hàm này trả về …”.
3. Đánh dấu state lặp lại và ước lượng số lượng của chúng.
4. Định nghĩa transition, miền hợp lệ, base case và sentinel cho state bất khả thi.
5. Viết memoization trước rồi test với các trường hợp nhỏ có thể vét cạn.
6. Suy ra thứ tự tabulation bằng cách đảo chiều mọi cạnh dependency.
7. Thêm reconstruction, sau đó mới cân nhắc nén bộ nhớ nếu output yêu cầu cho phép.

Sau khi giải, hãy đổi một constraint: cho phép đi chéo, thêm ô bị chặn, đếm số đường tối ưu hoặc giới hạn số lần phá chướng ngại vật. Mỗi thay đổi buộc ta kiểm tra state và evaluation order; đó mới là kỹ năng chuyển được sang bài tiếp theo.

Khi review, hãy đếm số state reachable, transition trên mỗi state, giá trị phải giữ và độ sâu đệ quy. Đừng suy complexity từ số loop nhìn thấy: state ba chiều có thể là bậc ba với một loop, còn table hai chiều có thể chỉ đi qua một tập thưa.

Những điểm cần giữ lại sau cùng là:

• State là bản tóm tắt nhỏ nhất nhưng đầy đủ để quyết định tương lai.
• Transition liệt kê các state nhỏ hơn có thể tới sau một quyết định.
• Base case là đỉnh đã có lời giải; invalid case biểu diễn cạnh bất khả thi.
• Memoization khám phá dependency DAG từ trên xuống; tabulation tính nó theo topological order tường minh.
• Reconstruction ghi lại hoặc phát lại transition đã tạo ra optimum.
• Complexity đến từ số state và công việc trên mỗi state, không đến từ hình dạng bề mặt của code.

Khi sáu mảnh này đã rõ, quy hoạch động không còn là pattern phải nhận diện bằng trí nhớ. Nó trở thành một đồ thị mà ta có thể tự thiết kế, tính toán, kiểm thử và giải thích.