面试如何对付DP题？

去年刚学的算法，接触到Dynamic programming时间不是很长。总感觉DP题就是找规律，把之前的结果recursive用起来。但是感觉面试的时候，很容易就找不出这种规律啊。求解面试的时候如何快速解出DP题。拜谢！

无他 唯手熟尔
共勉

chenyuhaohy 发表于 2016-3-26 16:06
没啊。求指教。查了一下。但是不知道短时间内怎么归纳出来。。有时候真的看不出来。

所谓动态规划无非就是：
大规模问题可以切割成小规模问题
小规模问题具有重复性

于是你从大规模问题开始分解，并且储存小规模问题的解，就是自顶向下动态规划

而你从小规模问题开始构造，拼凑成大规模问题，就是自底向上动态规划

至于怎么想到，只要给你一个问题，你会有意识地思考这个问题能否分解成较小规模的解，就基本达标了

到youtube 去搜 tushar dynamic programming
他有30 多个DP的视频，比算法导论讲得容易懂

动态规划其实是最简单的一类题目。。。

朋友，听说过数学归纳法吗？

staycrazy 发表于 2016-3-26 07:12
动态规划其实是最简单的一类题目。。。

朋友，听说过数学归纳法吗？

没啊。求指教。查了一下。但是不知道短时间内怎么归纳出来。。有时候真的看不出来。

staycrazy 发表于 2016-3-27 03:31
所谓动态规划无非就是：
大规模问题可以切割成小规模问题
小规模问题具有重复性

哦谢谢你的讲解！非常易懂！

好贴 观望 最近也在加强DP中