Cắt tỉa
Bài học 11 trên 15 trong khóa học Nhập môn quy hoạch động của Coddy.
Cắt tỉa là một kỹ thuật giúp giảm số phép tính mà thuật toán quy hoạch động cần thực hiện bằng cách tránh các phép tính không cần thiết. Kỹ thuật này loại bỏ một số nhánh của cây đệ quy không thể dẫn đến lời giải tốt hơn lời giải tốt nhất đã tìm được cho đến lúc đó. Bạn có thể dùng cắt tỉa trong cả thuật toán quy hoạch động từ trên xuống và từ dưới lên.
Thử thách
Chuyên giaTrong thử thách này, bạn được cho một ma trận số nguyên và một giá trị mục tiêu. Nhiệm vụ của bạn là chọn một số nguyên từ mỗi hàng của ma trận sao cho giá trị tuyệt đối của hiệu giữa giá trị mục tiêu và tổng các số nguyên đã chọn là nhỏ nhất. Sau đó, bạn cần trả về giá trị tuyệt đối nhỏ nhất này.
Tự làm thử
def minimize_difference(mat, target):
# Viết code ở đâyTấ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ực3Thuật toán quy hoạch động
Dãy con chung dài nhấtBài toán cái ba lôBài toán đổi tiềnKhoảng cách chỉnh sửaTự luyện tập: Trình biên dịch Python online