image.png
image.png

一、分治，回溯，递归，动态规划

1.1、递归的代码模板

image.png

1.2、分治（Divide & Conquer）的代码模板

image.png

1.3、联系

1、动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构）。
2、共性：找到重复子问题。
3、差异性：最优子结构，中途可以淘汰次优解。

1.4、本质

本质都是在寻找重复性，将重复性转化为 计算机指令集if else, for, loop, while ...

1.5、总结

1、人肉递归低效，很累。
2、找到最近最简方法，将其拆解成可重复解决的问题。
3、数学归纳法思维（抵制人肉递归的诱惑），先看n=1，n=2时的情况，然后看f（n）和f（n-1）之间的联系。

二、动态规划

2.1、定义

1、动态规划的英文叫Dynamic programming，翻译过来叫动态规划，翻译很玄学，其实翻译成动态递推更容易理解。
2、动态规划的本质就是将一个复杂问题拆解成若干个子问题进行解决。原文为:Simplifying a complicated problem by breaking it down into simpler sub-problems.
3、动态规划其实就是分治+ 最优子结构( Divide & Conquer + Optimal substructure)。

2.2、关键点

1、最优子结构：公式为，opt[n] = best_of(opt[n-1], opt[n-2], ...)
2、储存中间状态：opt[i]
3、递推公式（美其名曰：状态转移方程或者DP方程）：Fib：opt[i] = opt[n-1] + opt[n-2]. 二维路径为 opt[i,j] = opt[i+1][j] + opt[i][j+1] , 其中，需要判断opt[i,j]是否为空。

2.3、小结

1、打破自己的思维惯性
2、理解复杂逻辑的关键
3、职业进阶的要点要领

三、实战例题

1、斐波拉契数列
2、路径计数
3、最长公共子序列

---

数据下载：

• 1、动态规划脑图下载
• 2、实战列题下载