Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 có nội dung trình bày giới thiệu về dynamic programming, giải thuật dynamic programming, nguyên tắc của dynamic programming, chuỗi ma trận fully parenthesized, nhân hai ma trận, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Dynamic Programming Ch. 1 Dynamic Programming 1 Giôùi thieäu Dynamic programming giaûi baøi toaùn baèng caùch keát hôïp caùc lôøi giaûi cuûa caùc baøi toaùn con. ôû ñaây programming khoâng coù nghóa laø laäp trình . So saùnh dynamic programming vaø chia-vaø-trò divide-and- conquer Giaûi thuaät chia-vaø-trò chia baøi toaùn thaønh caùc baøi toaùn con ñoäc laäp giaûi chuùng baèng ñeä quy keát hôïp chuùng ñeå coù lôøi giaûi cho baøi toaùn ban ñaàu. Giaûi thuaät dynamic programming caùc baøi toaùn con khoâng ñoäc laäp vôùi nhau chuùng coù chung caùc baøi toaùn con nhoû hôn. giaûi moãi baøi toaùn con chæ moät laàn vaø ghi nhôù lôøi giaûi ñoù trong moät baûng ñeå truy caäp khi caàn ñeán. Ch. 1 Dynamic Programming 2 Baøi toaùn toái öu Baøi toaùn toái öu coù theå coù nhieàu lôøi giaûi moãi lôøi giaûi coù moät trò Tìm lôøi giaûi coù trò toái öu cöïc tieåu hay cöïc ñaïi . Ch. 1 Dynamic Programming 3 Nguyeân taéc cuûa dynamic programming Moät giaûi thuaät dynamic programming ñöôïc xaây döïng qua boán böôùc 1. Xaùc ñònh caáu truùc cuûa moät lôøi giaûi toái öu. 2. Ñònh nghóa ñeä quy cho giaù trò cuûa moät lôøi giaûi toái öu. 3. Tính giaù trò cuûa moät lôøi giaûi toái öu töø döôùi leân bottom-up . 4. Xaây döïng lôøi giaûi toái öu töø caùc thoâng tin ñaõ tính. Ch. 1 Dynamic Programming 4 Nhaân moät chuoãi ma traän Cho moät chuoãi ma traän A1 A2 . An . Xaùc ñònh tích A1A2 An döïa treân giaûi thuaät xaùc ñònh tích cuûa hai ma traän. Bieåu dieãn caùch tính tích cuûa moät chuoãi ma traän baèng caùch ñaët giöõa ngoaëc pa renthesize caùc caëp ma traän seõ ñöôïc nhaân vôùi nhau. Moät tích cuûa moät chuoãi ma traän laø fully parenthesized neáu noù laø moät ma traän hoaëc laø tích cuûa hai tích cuûa chuoãi ma traän fully parenthesized khaùc vaø ñöôïc ñaët giöõa ngoaëc. Ví duï moät vaøi tích cuûa chuoãi ma traän ñöôïc fully parenthesized A AB AB C . Ch. 1 Dynamic Programming 5 Chuoãi ma traän fully parenthesized Ví duï Cho moät chuoãi ma .
