动态规划是这样一种算法范式：将复杂问题划分为子问题来求解，并且将子问题的结果保存下来以避免重复计算。如果一个问题拥有以下两种性质，则建议使用动态规划来求解。
1 重叠子问题（Overlapping Subproblems）
2 最优子结构（Optimal Substructure）
1 重叠子问题
类似于分治法，动态规划将子问题的解合并。当多次需要用到子问题的解时，应当考虑使用动态规划。在动态规划算法中，子问题的解被存放于一张表格中，借此来避免重复计算子问题的解。因此，当所遇到的问题并不存在重叠子问题时，再将子问题的结果存表将毫无意义，因为我们并不需要再用到此结果，显然，此类情况，动态规划将不再适用。例如，Binary Search 就不存在重叠子问题。观察以下 Fibonacci Numbers 的递归程序，将会发现不少重叠（common）的子问题被重复计算。
/* 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(3) 被调用了2次。我们完全可以将 fib(3) 的结果保存起来，等下次再需要用到的时候，直接使用已经保存下来的结果，而不是再次计算。有以下两种方式来保存子问题的解：
1 Memoization (Top Down)
2 Tabulation (Bottom Up)
1 记忆化（Memoization）——Top Down
记忆化的程序（memoized program）在其递归版本的基础上做了一些细微的改变：在计算子问题的解之前，先进行查表。我们可以使用 NIL 值来初始化一个 lookup table，每当需要一个子问题的解时，我们首先查表（look into the lookup table）。我们该子问题的解先前已经计算过并存于表中，那么我们直接返回该解，否则，我们计算该子问题的解，并将计算出来的解保存在 lookup table 中，以便下次重用。
下面是一个使用记忆化的 Fibonacci Number 的程序：
/* Memoized version for nth Fibonacci number */
#include<stdio.h>
#define NIL -1
#define MAX 100 int lookup[MAX]; /* Function to initialize NIL values in lookup table */
void _initialize()
{
int i;
for (i = 0; i < MAX; i++)
lookup[i] = NIL;
} /* 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));
getchar();
return 0;
}
2 制表（Tabulation）——Bottom Up
制表的程序（tabulated program），自底向上建立一张 lookup table，最终返回表中的最后一项纪录。
来看程序，同样是 Fibonacci Number ：
/* tabulated version */
#include<stdio.h>
int fib(int n)
{
int f[n+1];
int i;
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));
getchar();
return 0;
}
记忆化还是制表均可以用来保存子问题的解。在记忆化的版本中，我们只在需要时往 lookup table 中添加纪录，而在制表版本中，从第一项记录开始，所有记录都将依次被添加。与制表版本不同，记忆化版本的程序无须将所有记录添加至 lookup table 中。例如，LCS problem 的记忆化程序就无需添加所有记录。