Dynamic Programming I

解决方法:

• DFS: Traverse

• DFS: Divide Conquer

• Divide Conquer + Memorization

• Traditional Dynamic Programming

多重循环vs记忆化搜索

动态规划可以使用多重循环与递归的方式实现，但是多重循环比较容易理解。

自底向上vs自顶向下

两种方法没有太大优劣区别思维模式一个正向，一个逆向

什么情况下

使用
动态规划?

满足下面三个条件之一:

• ● 求最大值最小值

• ● 判断是否可行

• ● 统计方案个数

动态规划的四点要素

状态State

灵感，创造力，存储小规模问题的结果

方程Function

状态之间的联系，怎么通过小的状态，来算大的状态

初始化Initialization

最极限的小状态是什么,起点

答案Answer

最大的那个状态是什么，终点

面试中常见的动态规划类型

坐标型动态规划15%

序列型动态规划30%

双序列动态规划30%

划分型动态规划10%

背包型动态规划10%

区间型动态规划5%