动态规划例题众多详细讲解

《动态规划例题众多详细讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划参与竞赛的同学应由竞争关系和独立关系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转向合作学习的关系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）F(n)=1ifn=0or1F(n-1)+F(n-2)ifn>1n012345678910F(n)1123581321345589斐波纳契数列F(n)2递归vs动态规划递归版本:F(n)1ifn=0orn=1then2return13else4returnF(n-1)+F(n-2)动态规划:F(n)1A[0]=A[1]

2、←12fori←2tondo3A[i]←A[i-1]+A[i-2]4returnA[n]太慢!有效率!算法复杂度是O(n)3方法概要构造一个公式，它表示一个问题的解是与它的子问题的解相关的公式.E.g.F(n)=F(n-1)+F(n-2).为这些子问题做索引，以便它们能够在表中更好的存储与检索(i.e.,数组array【】)以自底向上的方法来填写这表格;首先填写最小子问题的解.这就保证了当我们解决一个特殊的子问题时,可以利用比它更小的所有可利用的子问题的解.由于历史原因,我们称这种方法为：动态规划.在上世纪40年代末(计

3、算机普及很少时),这些规划设计是与”列表“方法相关的.4动态规划算法算法思想将待求解的问题分解成若干个子问题，并存储子问题的解而避免计算重复的子问题，并由子问题的解得到原问题的解。动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法的基本要素：最优子结构性质和重叠子问题。原理5最优子结构性质：问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。对每个

4、子问题只解一次，然后将其解保存起来，以后再遇到同样的问题时就可以直接引用，不必重新求解。原理6动态规划解决问题的基本特征1.动态规划一般解决最值（最优，最大，最小，最长……）问题；2.动态规划解决的问题一般是离散的，可以分解（划分阶段）的；3.动态规划解决的问题必须包含最优子结构，即可以由（n－1）的最优推导出n的最优原理7动态规划算法的4个步骤：1.刻画最优解的结构特性.（一维，二维，三维数组）2.递归的定义最优解.（状态转移方程）3.以自底向上的方法来计算最优解.4.从计算得到的解来构造一个最优解.解决问题的基本步骤

5、原理8实例例题一.斐波纳契数列F(n)F(n)=1ifn=0or1F(n-1)+F(n-2)ifn>1步骤1：用F（n）表示在斐波纳契数列中第n个数的值；步骤2：状态转移方程：步骤3：以自底向上的方法来计算最优解n012345678910F(n)1123581321345589步骤4：在数组中分析构造出问题的解；9例题二.输入n，求出n！F(n)=1ifn=0or1F(n-1)*nifn>1步骤1：用F（n）表示n！的值；步骤2：状态转移方程：步骤3：以自底向上的方法来计算最优解n012345678910F(n)1126

6、24120720实例10例题三：排队买票问题一场演唱会即将举行。现有n个歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第i位歌迷买一张票需要时间Ti（1≤i≤n），队伍中相邻的两位歌迷（第j个人和第j+1个人）也可以由其中一个人买两张票，而另一位就可以不用排队了，则这两位歌迷买两张票的时间变为Rj，假如Rj

7、i-1个人买一张票，则前i-1个人的买票方式也一定是最优的。即问题的最优解包含子问题的最优解。12345i…in-1nn-2…步骤1：用F（i）表示前i个人买票的最优方式，即所需最短时间；现在要决定F(i)需要考虑两种情况：（1）第i个人的票自己买（2）第i个人的票由第i-1个人买步骤2：状态转移方程：min步骤3：以自底向上的方法来计算最优解12程序的实现BuyTicks(T,R)1n←length[T]2f[0]←03f[1]←T[1]4fori←2tondo5f[i]←f[i-2]+R[i-1]6iff[i]>f[

8、i-1]+T[i]then7f[i]←f[i-1]+T[i]8returnf13实例例题四：求最长不降子序列1．问题描述设有一个正整数的序列：b1,b2,…，bn，对于下标i1