本文共 2065 字，大约阅读时间需要 6 分钟。

1）重叠子问题 (Overlapping subproblems)

       像分治法一样，动态规划包含了对子问题的解决。动态规划主要用于不断地解决相同子问题。在动态规划中，子问题的计算解被存储在表中，使得这些不必重新计算。因此，当没有公共（重叠）子问题时，就不会使用动态规划。例如，二分搜索没有公共子问题。如果我们以斐波纳契数字的递归程序为例，有很多子问题会被反复解决。

/* simple recursive program for Fibonacci numbers */int fib(int n){   if ( n <= 1 )      return n;   return fib(n-1) + fib(n-2);}

       fib(5)的递归树如下：

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(0)

       我们可以看到函数 f(3) 被调用了2次。如果我们将存储 f(3) 的值，则不再计算它，我们可以重用旧的存储值。有以下两种不同的方法来存储值，以便可以重用这些值： 

       a）记忆（自上而下）：

       用于问题的记忆程序类似于具有小修改的递归版本，它在计算解之前查找查找表。我们初始化一个所有初始值为 NULL 的查找数组。每当我们需要解决子问题时，我们首先查找查找表。如果预先计算的值存在，那么我们返回该值，否则我们计算值，并将结果放在查找表中，以便以后可以重复使用。

       b）制表（自下而上） :

       给定问题的制表程序以自下而上的方式构建表，并返回表中的最后一个条目。例如，对于相同的斐波纳契数，我们首先计算fib（0），fib（1），fib（2），fib（3）等等。因此，从字面上看，我们正在建立自下而上的子问题的解决方案。

       以下是第n斐波纳契数字的记忆版本：

/* C/C++ program for Memorized version for nth Fibonacci number */#include
   
    #define NIL -1#define MAX 100int lookup[MAX];/* Function to initialize NIL values in lookup table */void _initialize(){    int i;    for (i = 0; i < MAX; i++)    {        lookup[i] = NIL;    }        return;}/* function for nth Fibonacci number */int fib(int n){    if (lookup[n] == NIL)    {        if (n <= 1)        {            lookup[n] = n;        }        else        {            lookup[n] = fib(n-1) + fib(n-2);        }    }    return lookup[n];}int main (){    int n = 40;    _initialize();    printf("Fibonacci number is %d ", fib(n));    return 0;}
   

       以下是第n个斐波纳契数字的表格版本：

/* C program for Tabulated version */#include
   
    int fib(int n){    int f[n+1];    f[0] = 0;    f[1] = 1;     for (i = 2; i <= n; i++)    {        f[i] = f[i-1] + f[i-2];    }    return f[n];}int main (){    int n = 9;    printf("Fibonacci number is %d ", fib(n));    return 0;}
   

       输出：

Fibonacci number is 34

       参考：

       还有一篇好的博文：，这里面中英对比解释比较好(๑•̀ㅂ•́)و✧

2）最佳子结构 (Optimal substructure)

       一个问题的最优解一定包含它子问题的最优解。

练习参考：

转载地址：http://ottai.baihongyu.com/