动态规划笔记

昨天在牛客网上做笔试题,碰到了一道题动态规划做了一晚上都没做出来,最后看着别人的答案才勉强做出来,太菜了,今天总结一下。 动态规划思路: 1、找到状态和选择,确定当前状态和转换 2、明确dp数组/或函数的定义,即dp数组保存了啥信息(dp数组一般是一维或二维) 3、寻找状态之间的关系,当前状态如何根据上一状态和一些已知信息得到(状态转换方程) 题目 外卖小哥的保温箱 从题目可以了解到,我们需要做的是: 1、找出需要的最少的k个保温箱,使得这个k个保温箱可以装下所有的货物; 2、确定转移货物的最少时间,所以所找到的k个保温箱中所包含的货物尽可能多,则需要转移货物就越少,时间越短; 输入代码: i