动态规划 (Dynamic programming) 是一种算法设计技巧，巧妙地利用它可以使得求解一个问题所需的时间、空间复杂度都大大减小，例如，假设我们要求 f(n), 而计算 f(n) 需要知道 f(n-1) 和 f(n-2), 这时我们就可以先计算 f(n-2), 再计算 f(n-1), 最后再计算 f(n).
我觉得 LeetCode 256 Paint House 问题是一个非常好的例子，用来介绍 DP 在算法设计中的应用。
有 n 个房子（n ≥ 1), 三种颜色的油漆（红、蓝、绿），需要对每个房子都用一种颜色油漆粉刷一遍，并且要求相邻两间房子用的油漆的颜色不同，例如房子 k 用了蓝色，那么房子 k+1 就不能再用蓝色了，只能用红色或者绿色，而且每个房子只能用 1 种油漆来粉刷，比如说不能同时用红色和蓝色两种油漆来粉刷一个房子。
现在有一个价目表 costs，是一个 n 行 3 列的矩阵，第一列对应红油漆的粉刷价格，第二列对应蓝油漆的，第三列对应绿油漆的，第 k 行对应房子 k, 例如 costs[k][0], costs[k][1], costs[k][2] 分别表示用红、绿、蓝三种颜色的油漆粉刷房子 k 的成本。
求粉刷这 n 个房子用的最少成本。
穷举（尝试每一可能种选项）然后求最小值的时间复杂度接近指数级别，是不可扩展的。
我们可以用 DP 的方法，设计出一种算法（解法），使得只遍历一遍价目表，就能得出答案（时间复杂度 O(n)）。
当 n == 1 时答案是显然的，因此我们总是假设 n ≥ 2.
我们用 f(j, k) 表示在不使用油漆 j 的情况下，粉刷房子 k 所需的最小成本，那么：
f(0, 0) = min(costs[0][1], costs[0][2])
f(1, 0) = min(costs[0][0], costs[0][2])
f(2, 0) = min(costs[0][0], costs[0][1])
也就是说 f(*, 0) 是可以轻易计算出来的。
而对于 f(j, k), 这里 j 取值为 0, 1, 或者 2, k 是任意一个大于 0 的整数。
我们有：
f(0, k) = min { costs[k][1] + f(1, k-1), costs[k][2] + f(2, k-1) }
f(1, k) = min { costs[k][0] + f(0, k-1), costs[k][2] + f(2, k-1) }