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

动态规划（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

}

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

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

评论

1 楼 从此醉 2014-03-10  

会算法的越来越少咯