斐波那契和动态规划

在基础算法领域，动态规划算是比较难得一类算法了，而且在算法竞赛或者面试中会有大量动态规划的题目，因此下功夫理解这个算法还是很有必要的。

斐波那契

斐波那契数组算是一个比较常见的讨论算法的入门题，在leetcode中也包含这个题目。

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
$F(N)=\begin{cases} 0 & N=0 \\ 1 & N=1 \\ F(N-1) + F(N-2) & N > 1 \end{cases}$
Given N, calculate F(N).
Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:0 ≤ N ≤ 30.

递归

显而易见的解法就是递归算法，不做解释，直接上代码：

func fib(N int) int {
  if N <= 1 {
    return N
  }
  return fib(N - 1) + fib(N - 2)
}

自上而下的优化解法

在递归算法中可以看到计算fib存在大量的重复计算，这些计算会占用很多时间。见下图：

15718946172954.jpg

图中对于 $F(2)$ 和 $F(3)$ 存在多次重复计算，我们是否可以通过缓存的方式减少重复计算呢？显然是可以的。实现也比较简单，只需初始化一个数组记录计算过的数据即可。
代码如下：

func fib(N int) int {
    if N <= 1 {
        return N
    }
    if N == 2 {
        return 1
    }
    Mem := make([]int, N + 1)
    Mem[0] = 0
    Mem[1] = 1
    Mem[2] = 1
    return f(N, Mem)
}

func f(N int, Mem []int) int {
    if ans := Mem[N]; ans > 0 {
        return ans
    }
    Mem[N] = f(N - 1, Mem) + f(N - 2, Mem)
    return Mem[N]
}

将计算过的数记录在Mem中，下次计算时先判断Mem是否存在，如果存在直接返回，否则计算。

自下而上的优化解法

上述优化算法解决了重复计算的问题，但是显然还是用到了递归。是否有进一步的优化空间呢？还是存在的。
我们可以先计算出需要的序列，等到调用时直接返回。代码如下：

func fib(N int) int {
    if N <= 1 {
        return N
    }
    if N == 2 {
        return 1
    }
    f := make([]int, N + 1)
    f[0] = 0
    f[1] = 1
    f[2] = 1
    for i := 3; i <= N; i++ {
        f[i] = f[i - 1] + f[i - 2]
    }
    return f[N]
}

这个算法比较清晰明了，不做解释。

动态规划

描述了这么多斐波那契的问题，和动态规划有什么联系吗？其实上面的两种优化算法就是动态规划的两种形式。
什么是动态规划呢？我们可以从分析上述解法入手。两种优化解法都用到了一个思路，就是记录之前的问题，不做重复计算。也就是把一个问题拆分成一个个小的问题，对小问题进行计算并保存，而复杂问题就是这些小问题的组合。
这就是动态规划的核心思路: Those who cannot remember the past are condemned to repeat it.
在总结动态规划之前，先来几个例子：

钢条切割

在《算法导论》中有一个钢条切割的问题：

Description
The rod-cutting problem is the following. Given a rod of length n inches and a table of prices $p_i$ for $i = 1，2，…，n$ , determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces. Note that if the price $p_n$ for a rod of length n is large enough, an optimal solution may require no cutting at all.
Example

length $i$ 1 2 3 4 5 6 7 8 9 10

price $p_i$ 1 5 8 9 10 17 17 20 24 30

length $i$	1	2	3	4	5	6	7	8	9	10
price $p_i$	1	5	8	9	10	17	17	20	24	30

下面进行一下分析：
长度为n的钢铁一共有 $2^{n+1}$ 中切割方式。假设将钢铁切割为k段（ $1\le k \le n$ ），则切割方案为 $n=i_1+i_2+...+i_k$ ，收益为 $r_n=p_{i_1}+p_{i_2}+...+p_{i_k}$ 。
不难看出，长度为n的钢铁的最佳方案可以拆解为长度为i和n-i两段的和的最佳方案 $0 \le i \le n$ ，即 $r_n = \max_{1 \le i \le n}(r_i + r_{n-i})$ 。从而我们可以将切割问题按照上述逐层拆解，即：
$r_n=\begin{cases} p_1 & n=1 \\ r_i + r_{n-i} & 1 < i \le n \end{cases}$

源码：

func cutRod(price map[int]int, n int) int {
    var r = []int{0}
    for i := 1; i <= n; i ++ {
        p := price[i]
        for j := 1; j <= i; j++ {
            tmp := r[j - 1] + r[i - j]
            if tmp > p {
                p = tmp
            }
        }
        r = append(r, p)
    }
    return r[n]
}

Maximum Subarray

这是leetcode上的一个题目：

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

分析：
假设以第i位 $0 \le i < len(nums)$ 结尾的子数组的最大和为 $p_i$ ，上述题目就是计算 $\max(p_i),0 \le i < len(nums)$ 。而 $p_i$ 可以表示为：
$p_i=\begin{cases} nums[i] & p_{i-1}<=0 \ or \ i = 0 \\ p_{i-1} + nums[i] & p_{i-1} > 0 \end{cases}$

源码：

func maxSubArray(nums []int) int {
    maxSum := []int{nums[0]}
    max := nums[0]
    for i := 1; i < len(nums); i++ {
        if maxSum[i - 1] < 0 {
            maxSum = append(maxSum, nums[i])
        } else {
            maxSum = append(maxSum, nums[i] + maxSum[i - 1])
        }
        if max < maxSum[i] {
            max = maxSum[i]
        }
    }
    return max
}

优化：
这个问题可以不对子问题进行存储，因此可以简化成：

func maxSubArray(nums []int) int {
    max, maxSum := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        if max < 0 {
            max = 0
        }
        max += nums[i]
        if maxSum < max {
            maxSum = max
        }
    }
    return maxSum
}

总结

从上述例子我们可以看到，动态规划问题的基本思想与分治法类似，将待求解的问题分解为若干个子问题，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供信息。动态规划解决的问题多数有重叠子问题这个特点。为降低反复计算。对每个子问题仅仅解一次，将其不同阶段的不同状态保存下来。适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的。
借用网上的总结，求解动态规划的问题的步骤如下：

划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。