我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划 >

超棒的DP问题详解之动态规划的思考角度

归档日期:04-23       文本归类:动态规划      文章编辑:爱尚语录

  那么什么是动态规划呢?如果一个解决问题的方法满足上面六个思考点中的前四个,那么这个方法就属于动态规划。而在思考动态规划方法时,后两点同样也是需要考虑的。

  面对问题要寻找动态规划的方法,首先要清楚一点,动态规划不是算法,它是一种方法,它是在一件事情发生的过程中寻找最优值的方法,因此,我们需要对这件事情所发生的过程进行考虑。而通常我们从过程的最后一步开始考虑,而不是先考虑过程的开始。

  打个比方,上面的挖金矿问题,我们可以认为整个开采过程是从西至东进行开采的(也就是从第0座开始),那么总有面对最后一座金矿的时候(第9座),对这座金矿不外乎两个选择,开采与不开采,在最后一步确定时再去确定倒数第二步,直到考虑第0座金矿(过程的开始)。

  因此在遇到一个问题想用动态规划的方法去解决时,不妨先思考一下这个过程是怎样的,然后考虑过程的最后一步是如何选择的,通常我们需要自己去构造一个过程,比如后面的练习。

  那么遇到问题如何用动态规划去解决呢?根据上面的分析我们可以按照下面的步骤去考虑:

  3、找到最后一步的子问题,确保符合“子问题重叠”,把子问题中不相同的地方设置为参数。

  6、确保满足“子问题独立”,一般而言,如果我们是在多个子问题中选择一个作为实施方案,而不会同时实施多个方案,那么子问题就是独立的。

本文链接:http://quangdungfc.net/dongtaiguihua/41.html