文档介绍：动态规划
Dynamic Programming
2
F(n) =
1 if n = 0 or 1
F(n-1) + F(n-2) if n > 1
n
0
1
2
3
4
5
6
7
8
9
10
F(n)
1
1
2
3
5
8
13
21
34
55
89
斐波纳契数列F(n)
3
递归 vs 动态规划
递归版本:
F(n)
1 if n=0 or n=1 then
2 return 1
3 else
4 return F(n-1) + F(n-2)
动态规划:
F(n)
1 A[0] = A[1] ← 1
2 for i ← 2 to n do
3 A[i] ← A[i-1] + A[i-2]
4 return A[n]
太慢!
效率高!
算法复杂度是 O(n)
4
方法概要
构造一个公式,它表示一个问题的解是与它的子问题的解相关的公式. . F(n) = F(n-1) + F(n-2).
为这些子问题做索引,以便它们能够在表中更好的存储与检索(., 数组array【】)
以自底向上的方法来填写这表格; 首先填写最小子问题的解.
这就保证了当我们解决一个特殊的子问题时, 可以利用比它更小的所有可利用的子问题的解.
我们称这种方法为:动态规划
5
动态规划算法
算法思想
将待求解的问题分解成若干个子问题,通过存储子问题的解而避免计算重复的子问题,并由子问题的解得到原问题的解。
动态规划算法通常用于求解具有某种最优性质的问题。
动态规划算法的基本要素:
最优子结构性质和重叠子问题。
原理
6
最优子结构性质:问题的最优解包含着它的子问题的最优解。
重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些问题被反复计算多次。动态规划算法对每个子问题只解一次,然后将其解保存起来,以后再遇到同样的问题时就可以直接引用,不必重新求解。
原理
7
动态规划
解决问题的基本特征
1. 动态规划一般解决最值(最优,最大,最小,最长……)问题;
2. 动态规划解决的问题一般是离散的,可以分解(划分阶段)的;
3. 动态规划解决的问题必须包含最优子结构,即可以由(n-1)的最优推导出n的最优
原理
8
动态规划算法的4个步骤:
1. 刻画最优解的结构特性. (一维,二维,三维数组)
2. 递归的定义最优解. (状态转移方程)
3. 以自底向上的方法来计算最优解.
4. 从计算得到的解来构造一个最优解.
解决问题的基本步骤
原理
9
实例
例题一. 斐波纳契数列F(n)
F(n) =
1 if n = 0 or 1
F(n-1) + F(n-2) if n > 1
步骤1:用F(n)表示在斐波纳契数列中第n个数的值;
步骤2:状态转移方程:
步骤3:以自底向上的方法来计算最优解
n
0
1
2
3
4
5
6
7
8
9
10
F(n)
1
1
2
3
5
8
13
21
34
55
89
步骤4:在数组中分析构造出问题的解;
10
例题二. 输入n,求出n!
F(n) =
1 if n = 0 or 1
F(n-1) *n if n > 1
步骤1:用F(n)表示n!的值;
步骤2:状态转移方程:
步骤3:以自底向上的方法来计算最优解
n
0
1
2
3
4
5
6
7
8
9
10
F(n)
1
1
2
6
24
120
720
实例