《动态规划学习笔记》是一份系统整理和总结动态规划算法原理及其应用的学习资料。它涵盖了从基础概念到高级技巧的内容,并通过实例解析帮助读者深入理解与灵活运用动态规划解决问题的方法。
昨天在牛客网上做了一道笔试题,用动态规划方法尝试了好久都没能解决,最后参考别人答案才勉强完成,感觉自己水平不够。今天打算总结一下。
动态规划的思路如下:
1. 确定状态与选择,并明确当前的状态和转换方式。
2. 明确dp数组或函数的意义,即它保存的信息(通常为一维或二维)。
3. 寻找状态之间的关系,通过上一个状态以及已知信息推导出当前状态。
题目是关于外卖小哥的保温箱问题。从题意可以看出:
1. 需要找出最少数量的k个保温箱来装下所有的货物;
2. 确定转移货物所需的最短时间,因此在所选中的这k个保温箱中尽可能多地放置货物,则需要进行的货物转移次数就越少,从而节省时间。