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