Khi nào dùng dynamic programming so với greedy?

Question

Accepted Answer

Cả DP lẫn greedy đều cần **optimal substructure**. Sự khác biệt: **greedy** còn yêu cầu **tính chất greedy-choice** (một tối ưu cục bộ là tối ưu toàn cục), trong khi **DP** cần thiết khi bạn phải xem xét **nhiều lựa chọn và các bài toán con chồng lấn**.

## Sự khác biệt

```text
Có optimal substructure?  -- cả hai đều cần
  + tính chất greedy-choice có thỏa?  -> GREEDY (nhanh, một lượt lựa chọn)
  + phải so sánh nhiều lời giải con / chúng chồng lấn?  -> DYNAMIC PROGRAMMING
```

## Đối chiếu kinh điển: đổi tiền

```python
# Greedy THẤT BẠI với bộ tiền {1,3,4}, số tiền 6 -> 4+1+1 (3 đồng)
# DP tìm ra tối ưu thực sự: 3+3 (2 đồng)
def min_coins(amount, coins):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)  # thử mọi đồng tiền
    return dp[amount]

min_coins(6, [1, 3, 4])               # -> 2
```

Greedy cam kết với một lựa chọn; DP khám phá tất cả và giữ lại cái tốt nhất.

## Khi nào áp dụng cái nào

- **Greedy:** lập lịch khoảng, Huffman, Dijkstra, MST — đã chứng minh tính chất greedy-choice.
- **DP:** knapsack, edit distance, đổi tiền tổng quát — các lựa chọn tương tác với nhau.

## Độ phức tạp

Greedy thường là O(n log n); DP đánh đổi nhiều thời gian/bộ nhớ hơn (thường O(n·m)) để lấy tính đúng đắn.

## Những cạm bẫy

Dùng greedy mà không chứng minh tính chất của nó cho ra **đáp án sai** nhưng vẫn vượt qua các test nhỏ. Khi nghi ngờ, hãy dùng DP hoặc kiểm chứng greedy với vét cạn.

## Tại sao điều này quan trọng

Chọn greedy khi nó hợp lệ tiết kiệm thời gian rất lớn; chọn nó khi không hợp lệ tạo ra các lỗi âm thầm.

Biết mô thức nào phù hợp — và có thể chứng minh điều đó — là một sự phân biệt ở cấp độ senior.

Nó ngăn cả việc over-engineering với DP lẫn việc under-delivering với một lựa chọn greedy không vững chắc.