Swift 算法实战之路:动态规划

[中文教程]
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看315 回复回复5 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 315|回复: 5
收起左侧

[中文教程] Swift 算法实战之路:动态规划

[复制链接]
代码买卖 发表于 2016-9-7 03:35:27 | 显示全部楼层 |阅读模式
快来登录
获取优质的苹果资讯内容
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
订阅梳理好了的知识点专辑
本帖最后由 代码买卖 于 2016-9-7 05:39 编辑


之前的算法之路,分析的问题大多比较具体简单 —— 可以直接套用一种方法解决。今天要讲的动态规划,其面对的问题通常是无法一蹴而就,需要把复杂的问题分解成简单具体的小问题,然后通过求解简单问题,去推出复杂问题的最终解。

Swift 算法实战之路:动态规划 0

Swift 算法实战之路:动态规划 - 敏捷大拇指 - Swift 算法实战之路:动态规划 0


形象的理解就是为了推倒一系列纸牌中的第100张纸牌,那么我们就要先推倒第1张,再依靠多米诺骨牌效应,去推倒第100张。

Swift 算法实战之路:动态规划 1

Swift 算法实战之路:动态规划 - 敏捷大拇指 - Swift 算法实战之路:动态规划 1

Domino Effect




1、实例讲解

斐波拉契数列是这样一个数列:1, 1, 2, 3, 5, 8, ... 除了第一个和第二个数字为1以外,其他数字都为之前两个数字之和。现在要求第100个数字是多少。


这道题目乍一看是一个数学题,那么要求第100个数字,很简单,一个个数字算下去就是了。假设F(n)表示第n个斐波拉契数列的数字,那么我们易得公式F(n) = F(n - 1) + F(n - 2),n >= 2,下面就是体力活。当然这道题转化成代码也不是很难,最粗暴的解法如下:

[Swift] 纯文本查看 复制代码
func Fib() -> Int {
  var prev = 0
  var curr = 1

  for _ in 1 ..< 100 {
    var temp = curr
    curr = prev + curr
    prev = temp
  }

  return curr
}


用动态规划怎么写呢?首先要明白动态规划有以下几个专有名词:

  • 初始状态,即此问题的最简单子问题的解。在斐波拉契数列里,最简单的问题是,一开始给定的第一个数和第二个数是几?自然我们可以得出是1
  • 状态转移方程,即第n个问题的解和之前的 n - m 个问题解的关系。在这道题目里,我们已经有了状态转移方程F(n) = F(n - 1) + F(n - 2)


所以这题要求F(100),那我们只要知道F(99)和F(98)就行了;想知道F(99),我们只要知道F(98)和F(97)就行了;想要知道F(98),我们需要知道F(97)和F(96)。。。,以此类推,我们最后只要知道F(2)和F(1)的值,就可以推出F(100)。而F(2)和F(1)正是我们所谓的初始状态,即 F(2) = 1,F(1) =1。所以代码如下:

[Swift] 纯文本查看 复制代码
func Fib(n: Int) -> Int {
  // 定义初始状态
  guard n > 0 else {
    return 0
  }
  if n == 1 || n == 2 {
    return 1
  }

  // 调用状态转移方程
  return Fib(n - 1) + Fib(n - 2)
}

print(Fib(100))


Swift 算法实战之路:动态规划 2

Swift 算法实战之路:动态规划 - 敏捷大拇指 - Swift 算法实战之路:动态规划 2

斐波拉契数列的动态规划

这种递归的写法看起来简洁明了,但是上面写法有一个问题:我们要求F(100),那么要计算F(99)和F(98);要计算F(99),我们要计算F(98)和F(97)。。。大家已经发现到这一步,我们已经重复计算两次F(98)了。而之后的计算中还会有大量的重复,这使得这个解法的复杂度非常之高。解决方法就是,用一个数组,将计算过的值存起来,这样可以用空间上的牺牲来换取时间上的效率提高,代码如下:

[Swift] 纯文本查看 复制代码
var nums = [Int](count: 100, repeatedValue: 0)

func Fib(n: Int) -> Int {
  // 定义初始状态
  guard n > 0