动态规划
初探动态规划
动态规划(dynamic programming)是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。
有两步关键的信息，首先问题是可以分解的也就是可以理解成，大问题是一系列子问题的解的和，子问题全部解决了，大问题也就解决了，过程是通过存储子问题的解来避免重复计算，所以它解决的是重复计算的问题，也就是类似于枚举，不同的是这个过程中我们避免了一些重复计算的枚举。
接下来，我们通过一个经典例题，通过不同的解法，分析并观察,来引入我们的主题-动态规划.
爬楼梯
给定一个共有n阶的楼梯，你每步可以上1阶或者2阶，请问有多少种方案可以爬到楼顶？
如图所示，若n=3,则一共有3种方案。
0->1->2->3, 0->2->3, 0->1->3
爬楼梯
本题的目标是求解方案数量，我们可以考虑通过回溯来穷举所有可能性。代码如下：
func backTrace(choice []int, res int, state, n int) int {
// 到达楼梯顶部，则方案数+1
if state == n {
res = res + 1
}
for _, step := range choice {
// 超过当前阶数，继续进行
if state + step > n {
continue
}
// 继续回溯
backTrace(choice, res, state, n)
}
return res
}
func climbStairsBackTrace(n int) int {
// 创建一个数组存放可选择的阶数
var choice = []int{1,2}
// 结果方案数
var res = 0
// 当前阶数
var state = 0
return backTrace(choice, res, state, n)
}
回溯算法通常并不显式的对问题进行拆解，而是将求解问题看作一系列决策步骤，通过试探和剪枝，搜索所有可能的解。
暴力搜索
现在我们尝试从问题分解的角度分析这道题。
设爬到第i阶共有dp[i] 种方案，那么dp[i] 就是原问题的解，其子问题包括：
dp[i-1]，dp[i-2]，dp[i-3]，dp[i-4]，dp[i-5]...，dp[2]，dp[1]
由于每次只能上1阶，或者2阶,当我们站在第i阶上时，上一轮只能站在第i-1,第i-2阶上，换句话说，我们只能从第i-1阶，或者第i-2阶迈向第i阶。
由此我们可以得出一个推论：爬到第i阶的方案数等于爬到第i-1阶和第i-2阶的方案数之和。公式如下：
dp[i] = dp[i-1] + dp[i-2]
这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得出来。如图所示:
递推关系
于是我们可以根据递推公式得到问题得解。以dp[n]为起点，递归地将一个较大问题拆解为两个较小问题的和，直至到达最小子问题dp[2],dp[1]时返回。其中，最小子问题的解是已知的，即dp[1] = 1, dp[2] = 2,表示爬到第1阶，第二阶方案数分别为1，2。以下是代码实现：
// 递推关系
func dfs(n int) int {
if n == 1 || n == 2 {
return n
}
return dfs[n-1] + dfs[n-2]
}
func climbStairsDFS(n int) int {
return dfs(n)
}
整个过程是一个递推过程。
下图展示了暴力搜索形成的递归树。对于问题dp[n]，其递归树的深度为n,时间复杂度为O(2^n),指数阶复杂度，如果n过大，那么复杂度会呈现爆炸式增长，对于程序而言会陷入漫长的等待。
暴力搜索递推树
观察图解，我们可以看到之所以呈指数增长，是因为有重叠子问题，子问题中包含子问题，无疑增加了时间复杂度。
记忆化搜索
为了提升算法效率，我们希望每个重叠子问题只被计算一次。为此，我们声明一个数组mem来记录每个子问题的解，并在搜索过程中将子问题剪枝。
- 当首次计算dp[i]时，我们将其记录至mem.
- 当再次计算dp[i]时，我们便可以从mem中获取结果，从而避免重复计算。
代码实现如下:
func dfs(n int, mem []int) int {
if n == 1 || n == 2 {
return i
}
// 剪枝，避免重复计算
if mem[n] != 0 {
return mem[n]
}
count = dfs(n-1, mem) + dfs(n-2, mem)
// 记录结果
mem[n] = count
return count
}
func climbStairsDFS(n int) int {
var mem = make([]int, n+1)
return dfs(n,mem)
}
如图所示，经过记忆化剪枝后，它的时间复杂度变为了O(n),所有重叠子问题只需要被计算一次。
climbing_stairs_dfs_memo_tree.png
记忆化搜索是一种“从顶至底”的方法:我们从原问题开始，递归的将较大子问题分解为较小子问题，直至最小子问题已知，之后通过回溯收集子问题的解，构建出原问题的解。
动态规划
与记忆化搜索方法相反，动态规划是一种“从底至顶的方法”:从最小子问题的解开始，迭代的构建更大子问题的解，直到原问题的解。
由于动态规划不包含回溯过程，因此只需要使用循环迭代实现，无须使用递归。同样，我们使用dp[n]来存储原问题的解，代码实现如下：
func climbStairs(n int) int {
if n == 1 || n == 2 {
return n
}
var dp = make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i ++ {
dp[n] = dp[n-1] + dp[n-2]
}
return dp[n]
}
下图展示了整个迭代过程：
climbing_stairs_dp.png
与回溯算法一样，动态规划也使用“状态”概念来表示问题求解的特定阶段，每个状态都对应一个子问题的解。例如，我们将爬楼梯问题的状态定义为当前所在楼梯阶数i，于是就有以下常用术语：
- 将数组dp[n]成为dp表，dp[i]表示状态i对应子问题的解。
- 将最小子问题对应的状态成为初始状态（第1阶和第2阶）。
- 将递推公式dp[i] = dp[i-1] + dp[i-2]成为状态转移方程。
空间优化
由状态方程可知，dp[i]只和dp[i-1]，dp[i-2]有关，我们无需使用数组来存储子问题的解，只需要两个变量向前滚动即可，代码如下:
func climbStairs(n int) int {
if n == 1 || n == 2 {
return n
}
a, b = 1, 2
for i := 3; i <= n; i ++ {
// a1 = 1,b1= 2,
// a2 = b1 = 2, b2 = 3,
// a3 = b2 = 3, b3 = a2 + b2 = 5,
// a4 = b3 = 5, b4 = a3 + b3 = 8,
// a存放上一次结算结果，b存放此次计算结果,所以需要将上一次b的值赋给a，上一次a+b的值赋给b
a, b = b, a+b
}
return b
}
观察以上代码，由于省去了dp数组占用的空间，空间复杂度由O(n)降O(1)。
在动态规划问题中，当前状态往往仅与前面有限个状态有关，这时我们可以保留必要的状态，通过降维”来节省空间。
这种空间优化技巧被称为“滚动变量”或"滚动数组".
本文参考：
初探动态规划
