0 写在前面

• 动态规划属于算法层面（是一种解决问题的思想），
• 递归是程序调用自身的编程技术（可以用来解决一部分动态规划的问题）

1 动态规划：

• 动态规划（DP 即 Dynamic Programming）本质指的是一类题型，说白了就是一个解决问题的思路——即一个大一点规模的问题可以被拆解为更小的，更容易解决的问题。
• 很多人把从大往小算（自顶向下）的形式称作递归，反过来从小往大（自底向上）算称为DP，但实际上只要满足大规模问题可以拆解为小规模问题，这个思路本身就是DP的，无非是顺序不一样罢了

1.1 自底向上（bottom - up、“DP”）

• 以自底向上为例，分析DP的优势、应用场景

所谓【动态规划】就是指知道了一组小规模问题的答案后，就可以用一个方案（状态转移方程）组装成大一点规模问题的答案的做法而已。为啥叫“动态”呢，因为状态转移会和几个条件相关，而不是一开始就可以无脑写死（无脑写死的一般就是贪婪）——贪婪选择 也是DP的思想：是特殊的DP。

尽管自顶向下和自底向上等价，但自顶向下算一个很容易发生的问题就是重复计算（大量重叠子问题），比如你为了算f(5)，普通的递归方式要重复计算很多很多次f(3), f(2)……。这些计算都是浪费的，实际表现比自底向上差的多（但再强调下，二者的思路没本质差别，仅仅是计算浪费不浪费的问题）

• 既然自顶向下计算很浪费，为啥我们还需要呢？

是因为很多数据结构不能直接从底向上访问，需要额外大量的存储空间和时间，并且这类数据结构的题型从顶往下分解问题更清晰直观（比如树、链表），反之强行自底向上拆解问题的思路实在太古怪，太反常识

1.1.1 leetcode动态规划问题

• 题目要求从左上走到右下（只能走右边或者下边），求中间最高的累计值

• 自底向上解决问题，没有重复子问题
  

• 这里官方题解定义f(i,j)递归函数，递归时与上一步f(i-1,j)和f(i,j-1)有关,
  

• 每一项的值只和上两项的值相关，时间复杂率O(2+2+…+2) = O(n)，n是递归的次数

1.2 自顶向下（top - down、“递归”）

• 还是上面那道题，我们定义递归函数f(i,j)，与下一步的值f(i+1,j)和f(i,j+1)有关，每一步都有两个下一步，中间很多步都是重复的下一步（重复计算），时间复杂度O(2ⁿ)，n是递归的次数

• 时间复杂度排序： $c<log2N<n<n\ast Log2N<n^2<n^3<2^n<3^n<n!$

• 自己写的递归只能通过不到一半的用例，显示超时！
  

• gitee主页：https://gitee.com/GZHzzz

• CSDN：https://blog.csdn.net/gzhzzaa

交流联系vx：

• Fighting!😎

while True:
	Go life

谢谢点赞交流！(❁´◡`❁)