本篇内容为浏览《算法导论》动静布局算法设计时的一些了解和记录。倡议大家去看原书，真的好。
动静布局有点像分治法，都是通过合并原问题的子问题的解来失去原问题的解。不同的是分治法将原问题划分为不相交的子问题，递归地解决子问题，而后组合它们的解来失去原问题的解。而动静布局须要原问题划分为有重叠的子问题，即其子问题又须要独特的子子问题。
当划分的子问题有重叠时，应用分治法会导致重叠子问题的反复计算。动静布局实际上就是通过存储子问题的解来防止这样的反复计算，这是动静布局的根本思维。
动静布局个别用于求一个最优解的问题，解决这样的问题蕴含四步：
- 演绎出一个最优解的构造。
- 递归定义一个最优解的值。
- 计算一个最优解的值。（个别应用从底向上的形式）
- 从结算中构建出最优解。
这样直白的语言概括其实很难了解的，还须要依据例子来了解，《算法导论》中给出了几个例子，咱们也借用他来记录一下。
例一
将一根长度为 n 的铁棒进行宰割，不同长度能够卖不同的价格（遵循一个价格表 P ），问能够卖出的最大的价格是多少？（一个最优解的问题）
设长度为 n 的铁棍通过切割最多能卖出的价格为 rn，第一次宰割的长度为 i ，其余部分为 n-i。其中 i 的范畴是 [1,n]，那咱们能够示意出 rn ：
rn = max (pi + rn-i)
留神i 的范畴是 [1,n]，这里的max要求的是例如p1 + rn-1，p2 + rn-2，... 之类的最大值。
很显然，这是个递归，咱们很容易写出代码（Go）：
func cutRod(p []int, n int) int { if n == 0 { return 0 } q := math.MinInt for i := 1; i <= n; i++ { q = max(q, p[i]+cutRod(p, n-i)) } return q}理论运行中，咱们会发现，效率十分非常低。。。为什么呢？因为计算中存在了大量的冗余，例如 n = 3 的计算过程须要 cutRod(p, 0),cutRod(p, 1),cutRod(p, 2)。而计算 cutRod(p, 2) 须要 cutRod(p, 1)，cutRod(p, 0)。计算 cutRod(p, 1) 须要 cutRod(p, 0)。这个过程中，很多雷同的函数计算了屡次。能够证实的是，该算法复杂度是指数级别的。
如何进行优化呢？ 直观的，咱们存储每个函数的执行后果，当发现执行的雷同的函数时，间接返回值就好，这是个空间换工夫的考量。先贴代码（Go）：
func cutRod(p []int, n int) int { var r []int for i := 0; i < n; i++ { r = append(r, math.MinInt) } return cutRodAux(p, n, r)}func cutRodAux(p []int, n int, r []int) int { if r[n] >= 0 { return r[n] } q := math.MinInt if n == 0 { q = 0 } else { for i := 1; i <= n; i++ { q = max(q, p[i]+cutRodAux(p, n-i, r)) } } r[n] = q return q}咱们额定开拓了一个数组 r 用来记录曾经计算过的函数的值，其中 r[n] 代表长度为 n 的铁棒通过切割最多能卖出的价格。
咱们这个办法是自上而下计算的，艰深一点，就是采纳递归的形式，我想要算 A，在计算过程中我发现须要 B 的后果，所以我压栈，而后去算 B。
递归是有老本耗费的。咱们能够选用自下而上的形式来防止这个耗费，即我曾经晓得 B 的后果了，我发现只须要一步就能算出 A，所以我只花了一步失去了A的后果。
自下而上能够间接应用循环的形式实现，先贴代码（Go）：
func cutRod(p []int, n int) int { var r []int r = append(r, 0) for j := 1; j <= n; j++ { q := math.MinInt for i := 1; i <= j; i++ { q = max(q, p[i]+r[j-i]) } r[j] = q } return r[n]}模式上看起来是不是更简略！自下而上中“最上面”的base case个别能够间接看进去，如这个例子中的 r[0]，显然等于 0。咱们依据这个base case，一直失去 r[1]，r[2]...，能够始终计算正无穷，然而咱们只须要计算到 n 即可满足咱们算法要求，也就是外层循环计算到 n 的起因。
自上而下就像深度优先搜寻。自下而上就像逆拓扑排序。
当咱们思考一个动静布局问题时，咱们应该了解所波及的子问题的汇合，以及子问题之间如何相互依赖。
之后咱们将持续介绍其余动静布局问题的案例，同时将摸索什么样的问题适宜用动静布局解决。