【思想】动态规划(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 ≈ 递归+记忆化+猜测
三、学习路线
- 币值最大化
- 硬币找零问题(贪心算法)
- 硬币收集
- 暴力递归(贪心失效)
- 避免递归重复计算(递推=递归+记忆化)
- 背包问题
- 完全背包
- 子数组问题
- 子序列问题
- 买卖股票
- 最长递增子序列问题
- 最大子数组问题
- 最优子结构与状态依赖
本文讲解了动态规划的思想的推演以及学习实践路径,后续会增加实践的算法题目!