Ôn tập các khái niệm chính

Bài học 14 trên 15 trong khóa học Nhập môn quy hoạch động của Coddy.

Trong bài học này, chúng ta sẽ ôn lại các khái niệm chính đã học trong khóa học Dynamic Programming 101.

Quy hoạch động: Quy hoạch động (dynamic programming) là một kỹ thuật giải các bài toán tối ưu bằng cách chia chúng thành các bài toán con đơn giản hơn và chỉ giải mỗi bài toán con một lần.
Ghi nhớ kết quả: Ghi nhớ kết quả (memoization) là một kỹ thuật tránh tính toán dư thừa bằng cách lưu kết quả của các lần gọi hàm tốn nhiều chi phí, rồi trả về kết quả đã lưu khi đầu vào giống nhau xuất hiện lần nữa.
Điền bảng: Điền bảng (tabulation) là một kỹ thuật giải các bài toán quy hoạch động bằng cách lần lượt điền các lời giải vào một bảng hoặc mảng, tiến dần đến lời giải cuối cùng.
Cấu trúc con tối ưu: Một bài toán có cấu trúc con tối ưu nếu lời giải tối ưu của bài toán chứa các lời giải tối ưu cho những bài toán con của nó.
Các bài toán con chồng lặp: Một bài toán có các bài toán con chồng lặp nếu có thể chia bài toán thành các bài toán con cùng dùng chung những bài toán con nhỏ hơn.
Tối ưu hóa bộ nhớ: Tối ưu hóa bộ nhớ (space optimization) là một kỹ thuật giảm lượng bộ nhớ cần thiết cho thuật toán quy hoạch động bằng cách chỉ theo dõi trạng thái cần thiết.
Che mặt nạ bit: Che mặt nạ bit (bit masking) là một kỹ thuật sử dụng thao tác trên bit để biểu diễn một tập hợp phần tử dưới dạng số nhị phân.
Cắt tỉa: Cắt tỉa (pruning) là một kỹ thuật giảm số phép tính cần thiết cho thuật toán quy hoạch động bằng cách tránh các phép tính không cần thiết.

Thử thách

Trung bình

Thử thách ôn tập: đường đi có chi phí thấp nhất

Bạn được cho một lưới n x n biểu diễn bản đồ thành phố. Mỗi ô trong lưới biểu thị một giao lộ, còn các giá trị trong ô biểu thị chi phí đi qua giao lộ đó. Bạn muốn đi từ góc trên bên trái của lưới đến góc dưới bên phải, và tại mỗi giao lộ, bạn chỉ có thể đi xuống hoặc sang phải.

Viết một hàm min_cost_path(grid) nhận lưới làm đầu vào và trả về chi phí thấp nhất để đi từ góc trên bên trái đến góc dưới bên phải của lưới.

Ví dụ:

grid = [
	[1, 3, 1],
	[1, 5, 1],
	[4, 2, 1]
]

min_cost_path(grid) => 7

Giải thích: Đường đi có chi phí thấp nhất là 1 -> 3 -> 1 -> 1 -> 1, với tổng chi phí là 7.

Tự làm thử

def min_cost_path(grid):
    # Viết code ở đây

Tất cả bài học trong Nhập môn quy hoạch động

1Giới thiệu về quy hoạch động

Quy hoạch động là gì?Vì sao quy hoạch động quan trọng?Ứng dụng trong nhiều lĩnh vực

4Chủ đề nâng cao

Độ dài mảng con nhỏ nhất Cắt tỉa Tối ưu hóa bộ nhớ Mặt nạ bit

2Khái niệm cơ bản

Ghi nhớ kết quả Ghi nhớ kết quả không dùng đệ quy

5Tổng kết

Ôn tập các khái niệm chínhTóm tắt

3Thuật toán quy hoạch động

Dãy con chung dài nhất Bài toán cái ba lô Bài toán đổi tiền Khoảng cách chỉnh sửa

Tự luyện tập: Trình biên dịch Python online