算法设计与分析-4动态规划金罐游戏报告.doc

仅供参考，copy冲查重塔峰。 算法设计与分析-4动态规划金罐游戏报告.doc （1） 动态规划算法设计思想。 （2） 金罐游戏问题的动态规划解法。 通过本次实验，我尝试了使用蛮力法（简单重复递归）和动态规划解决金罐问题，在该过程中我加深了对于动态规划算法的理解和运用。我认识到动态规划其实是在简单重复递归的逻辑增加状态数组，通过对状态数组的求解而免去重复递归的资源和时间消耗，从而获得解。 动态规划算法的关键就是将问题分解为子问题，并找到两者之间的状态方程。分解子问题的方法是找到最后一步。 另外通过蛮力法（时间复杂度O(2n)）和动态规划（时间复杂度O(n2)）的实际运行时间，加深对二者运算效率的理解。 在算法优化上，蛮力法也可借鉴动态规划的状态进行记录，避免重复调用，改进后可处理大数据但空间开销还是较大。动态规划求和步骤可提前做，同时在空间效率上可将二维数组压缩为一维数组。而将问题改为求当前序列相对最大金币值可避免求和开销。