Giao diện
Dynamic Programming Patterns
🎯 Mục tiêu
Luyện tập các mẫu quy hoạch động: bài toán leo cầu thang, ba lô 0/1, dãy con chung dài nhất, đổi tiền và nhân chuỗi ma trận.
Mô tả bài tập
Quy hoạch động (DP) là kỹ thuật giải bài toán bằng cách chia thành các bài toán con chồng lắp và lưu trữ kết quả. Bài tập này bao gồm 5 mẫu DP kinh điển.
Yêu cầu
Bài 1: Leo cầu thang (Climbing Stairs)
Cho n bậc thang, mỗi bước có thể leo 1 hoặc 2 bậc. Đếm số cách leo lên đỉnh.
python
def climb_stairs(n: int) -> int:
# TODO: Cài đặt DP bottom-up
pass
assert climb_stairs(2) == 2 # [1+1, 2]
assert climb_stairs(5) == 8Bài 2: Ba lô 0/1 (0/1 Knapsack)
Cho n vật phẩm với trọng lượng và giá trị, tìm giá trị lớn nhất chứa được trong ba lô sức chứa W.
python
def knapsack(weights: list[int], values: list[int], W: int) -> int:
# TODO: Cài đặt DP 2D hoặc tối ưu 1D
pass
assert knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8) == 10Bài 3: Dãy con chung dài nhất (LCS)
Tìm độ dài dãy con chung dài nhất của hai chuỗi.
python
def lcs(s1: str, s2: str) -> int:
# TODO: Cài đặt
pass
assert lcs("ABCBDAB", "BDCAB") == 4 # "BCAB"
assert lcs("ABC", "DEF") == 0Bài 4: Đổi tiền (Coin Change)
Cho các mệnh giá xu, tìm số xu ít nhất để đổi ra số tiền amount. Trả về -1 nếu không thể.
python
def coin_change(coins: list[int], amount: int) -> int:
# TODO: Cài đặt
pass
assert coin_change([1, 5, 10, 25], 30) == 2 # 5 + 25
assert coin_change([2], 3) == -1Bài 5: Nhân chuỗi ma trận (Matrix Chain Multiplication)
Cho kích thước các ma trận, tìm thứ tự nhân tối ưu để giảm thiểu số phép nhân.
python
def matrix_chain(dims: list[int]) -> int:
# TODO: Cài đặt DP khoảng
pass
assert matrix_chain([10, 30, 5, 60]) == 4500Phân tích độ phức tạp
| Bài | Time | Space |
|---|---|---|
| 1 - Climbing Stairs | O(n) | O(1) tối ưu |
| 2 - Knapsack 0/1 | O(n × W) | O(n × W) hoặc O(W) |
| 3 - LCS | O(m × n) | O(m × n) |
| 4 - Coin Change | O(n × amount) | O(amount) |
| 5 - Matrix Chain | O(n³) | O(n²) |
Gợi ý
Gợi ý Bài 2
Công thức: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi). Có thể tối ưu xuống mảng 1D bằng cách duyệt w từ W về 0.
Gợi ý Bài 4
Gọi dp[i] là số xu ít nhất để đổi ra i. Với mỗi mệnh giá c: dp[i] = min(dp[i], dp[i-c] + 1).
Gợi ý Bài 5
Gọi dp[i][j] là chi phí tối thiểu nhân ma trận từ i đến j. Thử mọi điểm chia k: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]).
Lời giải tham khảo
Xem lời giải
python
def climb_stairs(n: int) -> int:
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
def knapsack(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if c <= i and dp[i - c] + 1 < dp[i]:
dp[i] = dp[i - c] + 1
return dp[amount] if dp[amount] != float('inf') else -1