动态规划与分治类似，都是通过拆分成子问题再组合来得到结果，但是分治将问题划分成了互不相关的子问题，而动态规划适用于子问题重叠的情况。动态规划通常用来求解最优解。
原理
对于适用于动态规划的问题，要求其满足 最优子结构 和 子问题重叠 两个要素。
最优子结构
最优子结构指的是对于一个规模的最优解，其包含的每个子问题都是最优解。有了这一性质就保证了我们可以先求解子问题的最优解，再用它来构造原问题的最优解。
“剪切-粘贴”法可以用来证明一个问题是否有最优子结构。先假设一个最优解的子问题并不是最优解，那么我们可以“剪切”掉非最优解，将最优解“粘贴”进去，如果得到一个更优的解，那么就具有最优子结构。
这一点就要求了 无后效性，即一个子问题的解不受到规模变大的影响，当解确定后就不会再改变。
子问题重叠
子问题重叠是动态规划算法相比朴素算法能够提升效率的关键。以求解 Fibonacci 数列为例
1
2
3
4
5
int Fibonacci(int n){
if (n == 0 || n == 1)
return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
这是一个很普通的以递归方式求 Fibonacci 数列的代码，但是当我们仔细分析递归过程后
\[\begin{align} Fib(5) & = Fib(4)+Fib(3)\\ & = (Fib(3)+Fib(2))+(Fib(2)+Fib(1))\\ & = ((Fib(2)+Fib(1))+(Fib(1)+Fib(0)))+((Fib(1)+Fib(0))+Fib(1))\\ & = (((Fib(1)+Fib(0))+Fib(1))+(Fib(1)+Fib(0)))+((Fib(1)+Fib(0))+Fib(1))\\ \end{align}\]随着递归的深入，可以看到许多子问题，例如 Fib(2) 被反复求解，这种情况就被称为子问题重叠。动态规划算法则将子问题的结果放到一个表中，下一次再遇到时直接查表而非再次计算，通常这一做法可以将指数级的复杂度降到多项式级。
流程
有了这几个性质保证，动态规划的流程可以划分为：
- 刻画最优解的结构特征：寻找最优子结构
- 递归地定义最优解的值：利用最优子结构得到最优解与子问题最优解之间的关系
- 计算最优解的值：利用递归式计算，通常会采用自底向上的方法，也可以用递归加上簿记
- 构造最优解：又是还需要知道如何得到最优解就需要这一步骤，通常需要计算时保留更多的信息