Tuyệt chiêu 'Chia để trị' kết hợp bộ nhớ đệm: Nhớ lại quá khứ để không phải cắn răng tính lại.
data_objectQuy tắc: Robot chỉ được đi Sang Phải hoặc Đi Xuống. Tìm đường nhặt nhiều tiền nhất.
table_chartLý thuyết cốt lõi
Thuật toán này mô tả cách tiếp cận "Kẻ lập bảng". Thay vì mò mẫm toàn bộ đường đi cực kỳ tốn thời gian, DP sẽ duyệt qua từng ô và lưu lại kỷ lục (tổng cao nhất) vào bộ nhớ (Memoization).
DP[hàng][cột] = max( DP[hàng trên], DP[cột trái] ) + Tiền tại ô hiện tại
inventory_2Ứng dụng thực tế
functionsMật mã học & Chuỗi gen: Bài toán chuỗi con chung dài nhất (LCS) áp dụng trực tiếp để tìm sự tương đồng DNA.
shopping_bagBài toán cái Balo (Knapsack): Sắp xếp đồ vật lên xe tải sao cho giá trị chở được là đắt tiền nhất.
chat_bubble Bình luận (0)