与分治法的异同

共同点

二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解.

不同点

分治法将分解后的子问题看成相互独立的，通过用递归来做。
动态规划将分解后的子问题理解为相互间有联系,有重叠部分，需要记忆，通常用迭代来做。

原理

动态规划问题具有下列两个性质。

  1. 最优子结构
    如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。
  2. 重叠子问题
    在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

两种形式

①自顶向下的备忘录法 ②自底向上

举例：求Fibonacci数列

一、不用动态规划
会产生大量重复解，比如求解f(3),则要求解f(2)+f(1)，而f(2)又要求解f(1)，所以f(1)被重复求解。

  1. int fib(int n) {
  2.     if(n <= 0)    return 0;
  3.     if(n == 1)    return 1;
  4.     return fib(n-1) + fib(n-2);
  5. }

二、 自顶向下的备忘录法
还是利用递归，但是将各个子问题存在备忘录中，防止多次重复求解。但是递归会用到栈，产生额外开销。

  1. int fib(int n, int []arr) {
  2.     if(arr[n])    return arr[n];    //求出，直接返回
  3.     if(n <= 2)    arr[n] = 1;
  4.     else    arr[n] = fib(n-1, arr) + fib(n-2, arr);
  5.     return arr[n];
  6. }
  8. int main(){
  9.     cin>>n;
  10.     int* arr = new int[n+1];
  11.    memset(0, sizeof(arr));
  12.    relsult = fib(n, arr);
  13. }

三、自底向上
不用递归，求出一个个子问题最优解，进而得出最优解。

  1. int main(){
  2.     cin>>n;
  3.     int* arr = new int[n+1];
  4.     arr[0] = 1;    arr[1] = 1;
  5.     for(int i=2; i<=n; i++) {
  6.         arr[i] = arr[i-1] + arr[i-2];
  7.     }
  8.     return arr[n];
  9. }

空间进一步压缩

  1. int main() {
  2.     cin>>n;
  3.     int m1 = 0, m2 = 1, m = 1;
  4.     for(int i=2; i<=n; i++) {
  5.         m = m1 + m2;
  6.         m1 = m2;
  7.         m2 = m;
  8.     }
  9.     return m;
  10. }

三种模型

  1. 线性模型 状态的分布呈线性
  2. 区间模型
    区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。
  3. 背包模型