动归思想
递归，动归都是一种思想。而分治是一种算法。
子问题，通常规模更小，更容易求出答案
说到动态规划，其实离不开递归的思想，也就是把问题拆解成子问题
动态规划，是将复杂的问题，递归拆解成最优子问题，避免重复计算的编程方法
那这里隐含两个要素:
- 最优子问题
- 重复计算, 倘若计算过程没有重复，那就变成了分治算法了
以斐波那契额数列为例F(n) = F(n - 2) + F(n - 1)
f(5)
/ \
'f(3)' f(4)
/\ /\
f(1) f(2) f(2) 'f(3)'
- 其中F(5)可以通过子问题F(3) + F(4)得出
- 关键是，图中f(3)等节点的计算包含重复，而且是整棵树的重复
至顶向下
方向: 从”大问题”到”小问题”
也就是正常的递归+记忆化搜索，优点可能是比较容易想到，缺点可能会栈溢出，无法优化空间
每当遇到一个计算，先看表里有没有已经算好的，如果有就直接用上。
没有的话，计算好后，放入表中，等待将来查找
from functools import lru_cache
class Solution:
@lru_cache(maxsize=None)
def fib(self, N: int) -> int:
if N < 2:
return N
return self.fib(N - 2) + self.fib(N - 1)
至底向上
方向: 从”小问题”到”大问题”
- 最后一步(是怎样能够得到答案的)
- 化成子问题(得到初始条件与边界)
状态定义
F(N) = 斐波那契额数列中第N个值
状态转换
F(N) = F(N - 2) + F(N - 1)
初始与边界条件
F(0) = 0, F(1) = 1
如果只求第一个，那么注意F(1)的初始化边界
计算方向
从0到N
代码实现
class Solution:
def fib(self, N: int) -> int:
dp = [0 for _ in range(N + 1)]
if len(dp) > 1:
dp[1] = 1
for i in range(2, N + 1):
dp[i] = dp[i - 2] + dp[i - 1]
return dp[N]
空间优化
至底向上的好处是：
- 时间复杂度好计算
- 有空间压缩的可能
由于动态规划计算都是有一定方向的，那么对于前面的dp数组保存的值，可能就用不上了，可以空间压缩
技巧: 每个地方取模就好了
class Solution:
def fib(self, N: int) -> int:
dp = [0 for _ in range(2)]
if len(dp) > 1:
dp[1 % 2] = 1
for i in range(2, N + 1):
dp[i % 2] = dp[(i - 2) % 2] + dp[(i - 1) % 2]
return dp[N % 2]
少数可以只用几个变量
class Solution:
def fib(self, N: int) -> int:
if N < 2:
return N
pre, cur = 0, 1
for i in range(2, N + 1):
pre, cur = cur, pre + cur
return cur
One More Thing
算法能够解决的问题非常有限，而思想应对的问题却千变万化
所以，这篇介绍非常简单，但实战远不止这些。
而真正思想的锻炼，是在实战中不断积累提高的
一个真正量变引起质变的过程
–End–