概念

一般来说, 我们需要解决的问题大多数都较为直接, 可以用一种方法或思路直接了当的完成. 然而在开发过程中, 会遇到些许无法一次性解决的的复杂问题. 此时我们就需要把复杂问题分解为若干个小问题, 再 step by step 地解决小问题, 从而去得出该复杂问题的最终解. 这就叫做"动态规划".

场景

已知斐波那契数列的第n项是第n - 1项与第n - 2项的的和, 该数列的前两项都是1, 求斐波那契数列的的第100项

最直接的想法是用循环的方式相加98次即可, 那么用动态规划应该怎么写呢？一般来说, 动态规划分为两步:
1）初始状态, 即此问题的最简单子问题的解. 在斐波那契数列中, 最简单子问题自然是第一项和第二项的值, 解均为1.
2）状态转移方程, 即第n个问题的解和之前的 n - m 个问题解的关系. 在斐波那契数列中, 我们已经有了状态转移方程 F(n) = F(n - 1) + F(n - 2).

所以要知道F(100), 我们计算出F(99)与F(98)相加即可; 知道F(99), 我们计算出F(98)与F(97)相加即可; 以此类推...最后, 我们不难得出只要知道F(2)和F(1)的值, 就可以计算出F(100). 而F(2)和F(1)正是初始状态, 均为1, 所以可以写出代码:

static func Fibonacci(_ index: Int) -> Int {
  // * 定义初始状态
  guard index > 0 else {
    return 0
    
  }
    
  if index == 1 || index == 2 {
    return 1
    
  }

  // * 调用状态转移方程
  return Fibonacci(index - 1) + Fibonacci(index - 2)
    
} 

警告⚠️

这种写法看起来简洁明了, 但存在一个问题: 存在大量的重复计算. 比如要计算F(100), 需要计算出F(99)与F(98); 要计算F(99), 需要计算出F(98)与F(97); 此时F(98)已经被计算了两次, 以此类推...不难发现这种写法的浪费了很多时间. 我们也很容易想到用一个数据模型记录下已经计算出的F(n), 牺牲空间来换取提高效率. 笔者使用的是字典, key为项数(n), value为值(F(n)). 代码如下：

static var recordDict: [Int: Int] = [
        0: 0,
        1: 1
] // * 此处虚构了一个值为0的第0项

static func sequenceFibonacci(_ index: Int) -> Int {

    if recordDict[index] == nil {
        
        let result = self.sequenceFibonacci(index - 2) + self.sequenceFibonacci(index - 1)
        
        recordDict[index] = result
        
    }
    
    return recordDict[index]!
    
}

虽然看上去高大上，但在实际应用中一定注意以下两点：

1）内存溢出：每一次递归, 程序都会将当前的计算结果写入内存中. 随着递归愈来愈深, 所占内存也愈来愈大. 若超过系统分配给当前进程的内存容量, App就会Crash.
2）数据溢出：动态规划是一种由简至繁的过程, 其中累积的计算结果有可能超过当前数据类型的最大值, 从而导致程序抛出异常.

我们在上面的场景中会遇到第二点. 程序会在计算到F(93)时因为Int型数据溢出Crash. 在Swift中, Int 类型只能表示介于 -9,223,372,036,854,775,808 到 +9,223,372,036,854,775,807的数. 而F(92)的结果已经是7,540,113,804,746,346,429, 所以F(93)一定超过了Int 类型所能表示的最大值.

当然我们也有相应的方法去避免这两个问题.
1）对付内存溢出, 我们可以把递归写成循环的形式来避免.
2）对付数据溢出, 我们可以在每次计算时加入数据溢出的检测, 及时抛出异常并结束计算.