动态规划

写此系列博客的榜样来自：leetcode cookbook

思考方式

萌新三步：思考回溯怎么写；改成记忆化搜索；1：1翻译成递推。

以下以打家劫舍为例，说明思考方式

1. 回溯：
   

2. 把递归的计算结果保存下来，
   

def rob():
    n=len(nums)
    cache=[-1]*n
    def dfs(i):
        if i<0:
            return 0
        if cache[i]!=-1:
            return cache[i]
        res=max(dfs(i-1),dfs(i-2)+nums[i])
        cache[i]=res
        return res
    return dfs(n-1)

3. 改为递推
   自底向上计算
   

def rob():
    n=len(nums)
    f=[0]*(n+2)
    for i,x in enumerate(nums):
        f[i+2]=max(f[i+1],f[i]+x)

空间优化：

背包问题

一般问题

我们有 $n$ 件物品和一个容量（capacity）为 $C$ 的背包，记第 $i$ 件物品的重量（weight）为 $w_i$，价值（value）为 $v_i$，求将哪些物品装入背包可使价值总和最大。

0-1 背包

如果限定每件物品最多只能选取 $1$ 次（即 $0$ 或 $1$ 次），则问题称为 0-1 背包问题。

完全背包

如果每件物品最多可以选取无限次，则问题称为 完全背包问题。

假设放入背包中的物品 $i$ 的数目为 $k_i$，则上述背包问题在数学上可表达为：

$$
\max \sum_{i=0}^{n-1} k_i \cdot v_i
$$

约束条件（subject to, s.t.）：

$$
\sum_{i=0}^{n-1} k_i \cdot w_i \le C
$$

并且：

$$
\begin{cases}
k_i \in {0,1} & \text{0-1 背包问题} \\
k_i \in {0,1,2,\dots,+\infty} & \text{完全背包问题}
\end{cases}
$$