Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Dynamic Programming: Rod Cutting and Change Making
This lecture covers dynamic programming concepts such as rod cutting and change making. It starts with an introduction to dynamic programming, followed by the optimal substructure and the dynamic programming algorithm for rod cutting. The lecture then delves into reconstructing an optimal solution for rod cutting and concludes with a summary of the process. Additionally, it explores the change-making problem, discussing how to make a given amount of money with the least number of coins of given denominations. The lecture emphasizes the application of dynamic programming in solving these optimization problems.