Java教程

算法提高——动态规划

本文主要是介绍算法提高——动态规划,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

动态规划01

一、什么是动态规划

  动态规划是一种用来解决一类最优化问题的算法思想。将一个复杂的问题分解成若干个子问题(有点像分治),然后综合子问题的最优解找到原问题的最优解(这里有点像贪心)。在求解每个子问题的时候,每个求解过的子问题会被记录下来,在求解同样的子问题时就会直接读取上次被记录的结果,从而免去了重复的计算。因为动态规划采用了分治思想,所以可以用递归来实现。当然也可以用递推方式实现。

 

二、动态规划的递归写法

   斐波那契数列就是一个典型的例子,定义为:F(n)=F(n-1)+F(n-2)(n>=2),F1=1,F0=1。求斐波那契的递归写法也很常见,只要把数学上的函数转为逻辑上的代码就可以了。

  朴素算法

int F(n){
  if(n==0 || n==1) return 1;
    else return F(n-1)+F(n-2);
}

  下面可以模拟一下这个算法,假设求n=4,会得出以下过程

  F(4)=F(3)+F(2) 向下递归

  F(3)=F(2)+F(1);F(2)=F(1)+F(0)向下递归

  F(2)=F(1)+F(0)向下递归

  F(1)=1;F(0)=1;向上返回

  其实使用一颗递归树能更直观的感受该代码

 

   很明显F(2)的值被计算了两次,而事实上随着n的增大重复计算的次数会越来越多,而这颗递归树会像一颗完全二叉树一样,注意,仅仅是趋于一颗完全二叉树,可以把F(4)这颗树想象成F(5)的一颗子树,F(5)的另一颗子树其实就是F(3),显然F(3)也是F(4)的一颗子树,所以有两颗重复子树在一棵树中,这大大增加了运行时间。

  对于朴素算法的时间复杂度分析,可以通过这颗递归树来算一下,每个节点只包含常数次的运算,而递归二叉树的高度是n,所以节点数近似等于2^n,所以时间复杂度可是用O(2^n)来表示。

  采用动态规划的斐波那契数列

  可以申请一块大小为n的存储空间,这些空间用来存放F(n)各个子树的值,当要再次求相同子树时可以直接从相应位置取值

  

int F(int n){
    if(n==0 || n==1) return 1;
    else if(dp[n] != -1) return dp[n];
    else {
        dp[n] = F(n-1)+F(n-2);
        return dp[n];
    }
}

  开始时可以构造一个数组dp[n],数组元素值用-1初始化。通过这个数组就将程序的时间复杂度降到了O(n)的级别

这篇关于算法提高——动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!