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

gaotong1991

浏览: 91361 次
来自: 北京

最近访客更多访客>>

u012363178

czj4451

qnlpkuge

zhxhcj

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

算法

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

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

1）重叠子问题：

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

1
/* simple recursive program for Fibonacci numbers */

2

int fib(int n)

3
{

4

   if ( n <= 1 )

5

      return n;

6

   return fib(n-1) + fib(n-2);

7
}

执行 fib(5) 的递归树

1

                         fib(5)

2

                     /             \

3

               fib(4)                fib(3)

4

             /      \                /     \

5

         fib(3)      fib(2)         fib(2)    fib(1)

6

        /     \        /    \       /    \

7

  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)

8

  /    \

9
fib(1) fib(0)

我们可以看到，函数f（3）被称执行2次。如果我们将存储f（3）的值，然后避免再次计算的话，我们会重新使用旧的存储值。有以下两种不同的方式来存储这些值，以便这些值可以被重复使用。

A）记忆化（自上而下）：
B）打表（自下而上）：

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

下面是记忆化存储程序：

01
/* Memoized version for nth Fibonacci number */

02
#include<stdio.h>

03
#define NIL -1

04
#define MAX 100

05
 
06

int lookup[MAX];

07
 
08
/* Function to initialize NIL values in lookup table */

09

void _initialize()

10
{

11

  int i;

12

  for (i = 0; i < MAX; i++)

13

    lookup[i] = NIL;

14
}

15
 
16
/* function for nth Fibonacci number */

17

int fib(int n)

18
{

19

   if(lookup[n] == NIL)

20

   {

21

    if ( n <= 1 )

22

      lookup[n] = n;

23

    else

24

      lookup[n] = fib(n-1) + fib(n-2);

25

   }

26
 
27

   return lookup[n];

28
}

29
 
30

int main ()

31
{

32

  int n = 40;

33

  _initialize();

34

  printf("Fibonacci number is %d ", fib(n));

35

  getchar();

36

  return 0;

37
}

一）打表（自下而上）

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

view source

01
/* tabulated version */

02
#include<stdio.h>

03

int fib(int n)

04
{

05

  int f[n+1];

06

  int i;

07

  f[0] = 0;   f[1] = 1;

08

  for (i = 2; i <= n; i++)

09

      f[i] = f[i-1] + f[i-2];

10
 
11

  return f[n];

12
}

13
 
14

int main ()

15
{

16

  int n = 9;

17

  printf("Fibonacci number is %d ", fib(n));

18

  getchar();

19

  return 0;

20
}