1. 动态规划

1.1. 什么是动态规划 (Dynamic Programming) 简称 DP

动态规划, 擅长解决多阶段决策问题, 利用各个阶段的递推关系, 逐个确定每个阶段的最优决策, 并最终得到原问题的最优策略

举个例子: 10级台阶, 每次可以上1级也可以上两级, 问上完一共有多少种可能?

这个问题可以反向思考, 到第10阶有哪些办法? 第8阶+2 或者第9阶+1, 也就是, 第10阶的办法=第9阶的方法数+第8阶的方法数

F(10) = F(9) + F(8)

F(10) = F(9) + F(8), 就是 F(10) 问题的最优解, 局部的贪心完美的将问题分解, 如果F(9)和F(8)都是最优解, 那么F(10)一定也是最优解了

分解到最后, 一定会变成 F(1), F(2) 这样的规模最简单的问题, 这两个问题不能再分解了

上面问题的状态转移方程为 F(n) = F(n-1) + F(n-2), 这就是解决问题的核心, 能够让状态动起来

状态使用表格储存起来, 实际上的DP是从简单问题往复杂问题变化的

不管之前的决策是否为最优的, 都必需保证从现在开始的决策是在之前的基础上最优. 具体来说, 我们默认 F(8), F(9) 是最优的, 在此基础上, 得到最优的F(10)

由上一条可以看到, 如果 F(8)的决策会影响到F(9)和F(10)的决策, 那么F(10)=F(8) + F(9)就不成立, 所以, 要一定保证每个觉得的决策仅受之前决策的影响, 但不影响之后的决策

我们可以使用贪心算法得到一个解, 但是不能保证得到的是最优解, 而DP可以得到最优解

状态方程: s[i, j] = max{s[i-1, j], s[i, j-vi] + pi}

其中 vi代表第i件物品所占体积, pi表示第i件物品的价值

动态规划是一种能够求解出全局最优解的算法, 所以其实相当于穷举搜索了所有的解空间, 但是为什么高效呢? 是因为使用了储存备忘录的方式, 相当于使用了剪枝判断, 对重复子问题完成了高效的处理