动态规划出现在很多算法题目里面,初学者入门并不容易,网上很多文章看了以后还是不是很理解什么的动态规划算法,就打算记录一下自己的笔记,用案例加详细说明的方式深入理解动态规划的核心思想。
以lletcode198题目为例(抢金店),不熟悉题目的同学可以百度一下~这是一个典型的动态规划类题目。
首先看非动态规划怎么实现:
- public class Solution{
- public int rob(int[] nums){
- return slove(nums.length,nums);
- }
- public int slove(int idx,int[] nums){
- int max = Math.max(nums[idx] slove(idx- 2,nums),solve(idx-1,nums));
- return max;
- }
- }
上面的代码是通常的暴力搜索解法,这个一定要理解。本质上暴力搜索都是递归问题。说到这里,大家可能会问,怎么还没提到动态规划呢?
我们仔细看上面的代码,会发现时间复杂度很高,为什么呢? 因为有大量的重复计算!做如下分析:
n -> (n-2,n-3,n-4,......) //n代表一开始抢第n家店,后面以此类推。。。
n-1 ->(n-3,n-4,.........)
这里,大家会发现,红色划线部分的店会重复计算,我们用动态规划就是希望去除冗余计算,降低时间复杂度。
怎么做呢?基本步骤如下:
1)设计暴力算法,找到冗余
2) 设计并存储状态(一维,二维,三维,甚至Map)
3) 递归式(状态转移方程)
4)自低向上计算最优解
一般的动态规划算法都需要以上流程,乍一看,写的啥,看不懂是吧,下面以这个题目为例详细解读这几个步骤,第一个步骤上面代码已经完成了,下面看第二步:之说以会重复计算,是因为我们没有保存已经计算过的店家,所有我们用一个中间状态来保留计算过的店家,以此防止重复计算,完整代码如下:
public class Solution{
- public static int[] result;//记录中间态
- public int rob(int[] nums){
result = new int[num.length-1];
for(int i =0;i<num.length-1;i ){
result[i] = -1;//初始化为,-1表示没有计算过
- }
- return slove(nums.length,nums);
- }
- public int slove(int idx,int[] nums){
if(result[ids]>=0{
return result[idx];//大于0,表示该位置计算过了,直接返回,该行代码很关键
- }
- int max = Math.max(nums[idx] slove(idx- 2,nums),solve(idx-1,nums));
- return max;
- }
- }
以上代码中,红色部分为第二部。设计了一个中间状态,好好体会吧~
下面看第三部代码:
max = Math.max(nums[idx] slove(idx- 2,nums),solve(idx-1,nums));
状态转移方程就是一个递归式。
到这里,应该理解了动态规划的核心啦,做一个小总结:
联系客服