【思想】动态规划(DP)
一、介绍
1.1、历史
简单来记，20世纪50年代美国数学家理查德·贝尔曼发明的，用于数学领域解决某类最优问题的重要工具，以及在计算机领域当作是一种通用的算法设计技术。其余历史可以参考麻省理工教材动态规划第一篇。
1.2、定义
【重点】如果问题是由交叠的子问题构成的，那么就可以用动态规划技术来解决它。
一般来说，子问题出现在对给定问题求解的递推关系中，这个递推关系中包含相同类型的更小子问题的解。DP建议对于交叠的子问题一次又一次的求解，不如对每个较小的子问题只求解一次并把结果记录在表中，这样就可以从表中得出原始问题的解。
1.3、熟知的数学应用
斐波那契数的经典问题
0，1，1，2，3，5，8，13，21，34....
我们从中可以发现的规律是什么？
【0】= 0，【1】=1，【2】=1，【3】=2，【4】=3
问题进行拆解，发现重叠子问题（颜色区域），符合我们定义，如果问题是由交叠的子问题构成的，那么就可以用动态规划技术来解决。
那么我们定义下子问题比如我们求F(n)=F(n-1)+F(n-2)，然后根据我们的公式进行猜测是否满足所有结果。发现n=0/1的时候，不满足。所以需要调整下公式。如下伪代码：
function(int n){
//递归退出条件
if (n < 1){
return n;
}else{
//递归
return function(n-1)+function(n-2);
}
}但是我们之前提到的一个问题，本质上说我们上述递归代码已经实现了基本功能，按照上图来看我们计算F(4)的时候，需要计算F(3)和F(2)，但是发现很多重叠子问题，如何解决重复计算呢？我们可以假设无论F(2)和F(3)谁先执行，前执行的将结果保留记忆下来，那么后执行的来计算的时候可以直接获取，这样就可以避免重复计算了。我们再来修改下伪代码：
mem = {}
function(int n){
//记忆化，避免重复求解计算
if(n in mem) return mem[n];
//递归退出条件
if (0 <= n < 1){
return n;
}else{
//记忆存储子问题的解
mem[n] = function(n-1)+function(n-2);
//递归
return function(n-1)+function(n-2);
}
}那么原问题是如何被解决的呢？实际上我们采用的是自底向上计算的逻辑当n=0/1的时候，从递归栈中开始计算，直到返回结果。
二、步骤建议
2.1、动态规划步骤5
- 定义子问题(个人理解为先将问题拆解，拆解到最小单元即为子问题)
- 猜测（解决方案的一部分，推导计算公式）
- 相关子问题解决方案（局部问题解决方案）
- 递归+记忆 （解决重复计算问题）
- 或建立DP表自下而上检查子问题的循环/拓扑顺序（状态转移方程）
- 解原问题：=子问题或通过组合子问题解 =>额外时间
来源：麻省理工针对动态规划推导步骤，动态规划第一篇，动态规划第二篇
2.2、精简下步骤
1、定义子问题-问题拆解
2、构建递推公式（递归+记忆化==>递推）
3、自底向上处理（状态转移方程）
4、DP ≈ 递归+记忆化+猜测
三、学习路线
- 币值最大化
- 硬币找零问题（贪心算法）
- 硬币收集
- 暴力递归（贪心失效）
- 避免递归重复计算（递推=递归+记忆化）
- 背包问题
- 完全背包
- 子数组问题
- 子序列问题
- 买卖股票
- 最长递增子序列问题
- 最大子数组问题
- 最优子结构与状态依赖
本文讲解了动态规划的思想的推演以及学习实践路径，后续会增加实践的算法题目！
