首页 > 代码库 > 简单动态规划问题分析

简单动态规划问题分析

例题:

1022: 菜鸟和大牛(csuoj)

像这一类问题,首先不管是属于什么类型的,如果是按照题目的思路一步步走下来,然后运行,最后肯定是要超时的,究其原因,它的时间复杂度很不合理,最后是呈现指数增长的方式的。ACM本来就是研究最优算法的,所以不管结果如何,这个方法绝对不是优先选择的。

然后通过由下向上进行分析求解,会发现虽然思考问题的方式改变并不大,但是最后的大部分结果在还没有进行大量的运算之前就被我们排除了。这个方法的名字并不重要,重要的是以后解题时这种方法都应该是自己优先考虑的。