前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >动态规划怎么用?

动态规划怎么用?

作者头像
爬蜥
发布2019-07-09 15:25:59
2.6K0
发布2019-07-09 15:25:59
举报
文章被收录于专栏:爬蜥的学习之旅

动态规划应该用于最优化问题

最优化问题指的是,解决一个问题可能有多种可行的值来解决问题,但是我们需要一个最优的(最大或者最小)值

动态规划适用于子问题不是独立的情况,即各个子问题之间包含公共的子问题。动态规划对每个子问题只计算一次,保存其计算结果到"一张表",重复利用,从而优化执行。

分治法则是把一个大的问题划分成一些独立的子问题,递归求解子问题的情况;贪心算法则是会先选择当时看起来是最优的选择,然后再求解一个结果的子问题

如何使用动态规划

代码语言:javascript
复制
fib(n):
    if n<=2:f=1;
    else: f= fib(n-1)+fib(n-2);
    return f;
复制代码

可以简要分析下这个执行过程:要去求解 fib(n),首先要知道fib(n-1)和fib(n-2),要计算fib(n-1)则需要知道fib(n-2)和fib(n-3),要计算fib(n-2)则需要知道fib(n-3)和fib(n-4),依此类推。 很明显可以看到:如果计算出了fib(n-1)的子问题和fib(n-2)的子问题存在依赖性,要计算fib(n-1)必然要计算fib(n-2);同时如果复用了fib(n-2)那么当计算fib(n-1)就非常简单,直接相加即可。这也就是复用子问题处理结果

代码语言:javascript
复制
fib(n):
    memo={}
    if n in memo:return memo[n];
    if n<=2:f=1;
    else f=fib(n-1)+fib(n-2);
    memo[n]=f;
    return f;
复制代码
代码语言:javascript
复制
int fib(int n){
        if(n<=2){
            return 1;
        }
        int f1=1,f2=1;
        for(int i=3;i<=n;i++){
            int f=f1+f2;
            f1=f2;
            f2=f;
        }
        return f2;
    }
复制代码

这种计算方式,它实际上是相当于进行了拓扑排序,即我只有先执行完fib(n-2),再执行fib(n-1),然后才执行fib(n)

分析下来可以发现:

拓扑排序

斐波那契数列中的拓扑排序,它本质上类似拓扑排序的DAG最短路径

要获取它的最短路径,过程如下

每条边都访问了一遍,然后初始化了每个顶点的值,它的运行时间为O(V+E)

计算过程可以看到:

一般的图拓扑排序为

对于DAG:

indegree(t):入度数也就是类似(u,t)边的数量,需要去遍历所有t的入边

O(1):判断是不是有入边

总共的执行时间为

解决图中有环的时候求最短路径的问题

所需要的展开层数为:|V|-1 对于求最短路径来讲,最长不能超过|V|-1,否则就是成环,会造成循环的情况(从0开始的计数),这就是为什么Bellman-Ford的外层循环是 |V|-1

从斐波那契和最短路径的例子看出,要使用最短路径,需要确保子问题之间是互相依赖的,这样能够重复利用子问题产生的结果,而要去重复利用子问题,那首要条件是找到子问题是什么?然后在多个子问题之间选择最优的结果,并按照拓扑排序的顺序进行计算

使用动态规划的一般步骤是什么?

  1. 定义子问题 :一般来讲子可以从输入条件来寻找,如果输入条件少了一项,我解决这个问题的方式会发生改变吗?如果不会,那么它基本就是子问题

计算子问题的数量

  1. 思考:明确要去尝试所有可能方式,选取最好的一个。选取中要思考
  • 获取到的输入项是否应该被选入子问题的结果之中?
  • 有什么途径能够使子问题扩展到原有的问题?
  • 子问题要计算原有的问题,增加了什么变化的因素?

计算选择的数量

  1. 关联所有的子问题:根据思考得到父子问题的关联关系

计算单个子问题所需要处理的时间

  1. 重用子问题结果并记下新的结果

计算总耗时

最终解决原有的问题,它消耗的时间为: 子问题的数量 * 每个子问题处理所需要时间

总的来说就是:尝试所有可能的子问题的结果,将最好的可能子结果存储下来,然后重复利用已经解决的子问题,递归去解决所有的问题(思考+记忆+递归)

一定要用动态规划吗?

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。比如

代码语言:javascript
复制
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
复制代码

乍看之下,要求连续最大和,首先得计算出子串的最大和,才能去计算原始数组的最大和,也就是说

  1. 子问题是:子数组的最大和
  2. 依赖关系:dp(i)=max(i,i+dp(i-1)),增加了一个新的元素扩展子问题,得到原问题,然后从扩展的结果和原有的结果中取获取一个最优解
  3. dp(i-1)是可以重用的
代码语言:javascript
复制
 public int maxSubArray(int[] nums) {
       int max=Integer.MIN_VALUE;
       Map<Integer,Integer> mem=new HashMap<>();
       for(int i=0;i<nums.length;i++){
       //按照一定顺序执行
           int v=dp(i,nums,mem);
           if(v>max){
               max=v;
           }
       }
        return max;
    }
    
    public int dp(int i,int[] nums,Map<Integer,Integer> mem){
        Integer v=mem.get(i);
        if(v!=null){
        //重用子问题的结果
            return v;
        }
        int sum = nums[i];
        if(i==nums.length-1){
            mem.put(i,sum);
            return sum;
        }
        //先计算子问题
       int cSum = dp(i+1,nums,mem);
       int tempV = sum+cSum;
       //明确父子问题之间的关系,存储新的子问题结果
       if(tempV<sum){
           mem.put(i,sum);
           return sum;
       }
        mem.put(i,tempV);
       return tempV;
    }
复制代码

分析可以看到,它的执行为需要遍历一遍整个的数组,然后要去计算的子问题包括 n-1,n-2,..,1,耗时为 O(n+n-1)=O(2n)=O(n),同时需要一个O(n)的空间存储。

代码语言:javascript
复制
  public int maxSubArray(int[] nums) {
       int max=nums[0]; 
        int currMax=nums[0];
        for(int i=1;i<nums.length;i++){
            int temp=nums[i]+currMax;
            if(temp>nums[i]){
                currMax=temp;
            }else{
                currMax=nums[i];
            }
            if(max<currMax){
                max=currMax;
            }
       }
        return max;
    }
复制代码

通过这种方式,使用的空间为O(1),时间就是O(n)。 由此可见动态规划本身只是一种解决问题的思想,并不是说动态规划得到的最优解就是解决问题的最佳方案

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年08月05日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 如何使用动态规划
  • 拓扑排序
    • 解决图中有环的时候求最短路径的问题
    • 使用动态规划的一般步骤是什么?
    • 一定要用动态规划吗?
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档