search

lewenweijia / notes

🏊 dive dive diving
1 stars 0 forks source link

重新认识DP #36

Open lewenweijia opened 4 years ago

lewenweijia commented 4 years ago

DFS + MEMO => DP => Greedy

贪心算法可以认为是DP的一个特例, 贪心算法需要满足更多的环境条件(贪心选择性质) 暴力(指数) => DP(多项式) => 贪心(线性) O(2^n) => O(N^2) => O(N)

废话?:

  1. 搜索, 那么搜索肯定会有一个搜索起点
lewenweijia commented 4 years ago 
有趣的是, 回溯在调用栈中的动态体现是一种波浪的形态, 代码层面是for + fn的操作

动态规划? 就是设置边界, 从起点开始, 根据状态方程将所有可能到达的状态都算一遍
DFS 和 动态规划的基础都是整个状态图

知道目标状态依赖什么状态

递归是DFS的一种实现方式, DFS是动态规划的一种实现方式, 回溯法是DFS过程中可选操作
回溯是递归时候自然产生的一种操作