首页 > 动态规划 > 动态规划(1)-重叠子问题的性质
2014
02-24

动态规划(1)-重叠子问题的性质

动态规划(DP)通过分解成子问题解决了给定复杂的问题,并存储子问题的结果,以避免再次计算相同的结果。我们通过下面这个问题来说明这两个重要属性:

1)重叠子问题
2)最优子结构

1)重叠子问题:

像分而治之,动态规划也把问题分解为子问题。动态规划主要用于:当相同的子问题的解决方案被重复利用。在动态规划中,子问题解决方案被存储在一个表中,以便这些不必重新计算。因此,如果这个问题是没有共同的(重叠)子问题, 动态规划是没有用的。例如,二分查找不具有共同的子问题。下面是一个斐波那契函数的递归函数,有些子问题被调用了很多次。

/* 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)记忆化(自上而下):
B)打表(自下而上):

一)记忆化(自上而下):记忆化存储其实是对递归程序小的修改,作为真正的DP程序的过渡。我们初始化一个数组中查找所有初始值为零。每当我们需要解决一个子问题,我们先来看看这个数组(查找表)是否有答案。如果预先计算的值是有那么我们就返回该值,否则,我们计算该值并把结果在数组(查找表),以便它可以在以后重复使用。

下面是记忆化存储程序:

/* 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;
}

一)打表(自下而上)

下面我们给出自下而上的打表方式,并返回表中的最后一项。

/* 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;
}

这两种方法都能存储子问题解决方案。在第一个版本中,记忆化存储只在查找表存储需要的答案。而第二个版本,所有子问题都会被存储到查找表中,不管是否是必须的。比如LCS问题的记忆化存储版本,并不会存储不必要的子问题答案。

ACM之家原创,文章链接:http://www.acmerblog.com/dynamic-programming-4577.html


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1