由浅入深讲解动态规划

文章来自于公众号,原地址https://mp.weixin.qq.com/s/lBXc_0YXhKxLsrGhNH80Mw
动态规划是一种常用的算法思想,很多朋友觉得不好理解,其实不然,如果掌握了他的核心思想,并且多多练习还是可以掌握的。下面我们由深入浅地来讲讲动态规划。

斐波那契数列

首先我们来看看斐波那契数列,这是一个大家都很熟悉得数列:

// f = [1, 1, 2, 3, 5, 8]
f(1) = 1;
f(2) = 1;
f(n) = f(n-1) + f(n-2)

递归版斐波那契数列

有了上面得公式,我们很容易写出计算f(n)得递归代码:
由浅入深讲解动态规划

现在我们考虑一下上面得计算过程,计算f(5)的时候需要f(4)和f(3)的值,而计算f(4)的时候需要f(3)和f(2)的值,这里f(3)就重复算了两遍。在我们已知f(1)和f(2)的情况下,我们其实只需要计算f(3),f(4),f(5)三次计算就行了,但是为了计算f(5),我们总共计算了8次其他的值,里面f(3),f(2),f(1)都有重复的多次计算。如果n不是5,而是一个更大的数,计算次数更是指数级增长,这个递归算法的时间复杂度是O(2n)。
由浅入深讲解动态规划

带记忆的递归的斐波那契数列

由浅入深讲解动态规划

非递归的斐波那契数列

为了解决上面指数级的时间复杂度,我们不能用递归算法了,而要用一个普通的循环。
由浅入深讲解动态规划

钢条切割问题

某公司出售钢条,出售价格与钢条的长度之间的关系如下图

长度i 1 2 3 4 5 6 7 8 9 10
价格pi 1 5 8 9 10 17 17 20 24 30

问题:现有一段长度为n的钢条和上面的价格表,求切割钢条的方案,使得总收益最大。

递归方案

以长度为5的钢条为例,假设只切一刀,情况有4种,

  • [1, 4]
  • [2, 3]
  • [3, 2]
  • [4, 1]
    分成了左右两部分,两部分又分别可以继续切,而每部分一切,又变成了两部分,又可以继续切。
    写成公式为:rn = max(pn, r1+rn-1, r2+rn-2, ... , rn-1+r1)
  • rn: 表示求解的目标
  • pn: 表示一刀也不切
  • r1 + rn-1: 表示左边为1, 右边为n-1长度的两端。
    由浅入深讲解动态规划

动态规划

由浅入深讲解动态规划

最长公共子序列的长度

一个序列的子序列是在该序列中删除若干元素后得到的序列,如ABCD和BDF都是ABCDEFG的子序列,不考虑连续。

递归方案

由浅入深讲解动态规划

动态规划

由浅入深讲解动态规划

上一篇:android设计模式总结,字节跳动算法工程师面试总结


下一篇:小程序架构设计(一)