贷款 东莞网站建设,编程用什么软件写代码,濮阳建设工程网站,法律网站开发目录 一、动态规划的定义二、动态规划的基本要素和主要步骤#xff08;一#xff09;最优子结构#xff08;二#xff09;重叠子问题 三、贪心法、分治法和动态规划的对比#xff08;一#xff09;贪心法#xff08;二#xff09;分治法#xff08;三#xff09;动态… 目录 一、动态规划的定义二、动态规划的基本要素和主要步骤一最优子结构二重叠子问题 三、贪心法、分治法和动态规划的对比一贪心法二分治法三动态规划 四、动态规划的递归和迭代法求解一由顶向下的递归法二由底向上的迭代法 五、动态规划的应用一斐波那契数列二汉诺塔三最优二叉查找树四矩阵连乘五0-1背包 一、动态规划的定义
动态规划的基本思想是将问题分成若干个子问题先求解子问题然后从子问题的解进而得到原问题的解。
二、动态规划的基本要素和主要步骤
动态规划算法的两个基本要素是最优子结构和重叠子问题其主要步骤如下 ①问题需要具有最优子结构性质 ②构造最优值的递归表达式 ③最优值的算法描述 ④构造最优解。
一最优子结构
问题可分为若干个子问题最优子结构指的是问题的最优解可以由其子问题的最优解求解出来它的也是依据将复杂问题分解成简单子问题的方法。总的来说某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。
二重叠子问题
当划分的子问题中有些子问题重复出现时这些问题是会被重复计算和求解的从而会导致算法效率低且造成空间开销而动态规划的优势在求解划分的重叠子问题的时候将第一次求解的解通过数组或表存储起来从而可以避免重复计算后面相同的子问题。
三、贪心法、分治法和动态规划的对比
一贪心法
每一步都选择当前最优解而不考虑该决策对整体的影响。贪心算法通常适用于简单、容易分解的问题即具有贪心选择性质和最优子结构两个重要的性质的问题求解。贪心法总是做出最好的选择可以快速地得到近似上的最优解的情况局部最优选择时间复杂度较低但其缺点是不能保证得到全局上的最优解。
二分治法
可分为分解、治理两大步骤其通常适用于优化问题采用递归的思想每次将问题分成两个或更多的小问题由于各个子问题是相互独立的所以通过递归最终合并可以很容易得到原问题的解但若各个子问题不是相互独立的时则会造成重复从而会有很高的时间复杂度。
三动态规划
与分治法不同的是动态规划通常解决的是重叠子问题性质和最优子结构性质的问题其中解决子问题只需一次解决后会将其解保存并重复使用避免重复计算。动态规划通常采用自底向上的方式通过先解决子问题再解决大问题的方式进行求解。动态规划适合用于优化问题并且能够保证得到全局最优解。但对比贪心法、分治法算法由于需要存储各种状态所以其需要的空间更大。
三种算法的对比如下表
名称贪心法分治法动态规划适用性一般问题优化问题优化问题求解线性求解递归求解递归和迭代求解求解顺序先选择后解决子问题先选择后解决子问题先解决子问题后选择特征由顶向下由顶向下由顶向下、由底向上最优子结构满足不满足满足子问题规模仅一个子问题所有子问题所有子问题子问题独立性仅一个子问题每个子问题独立每个子问题重叠不独立子问题最优解部分最优解全部最优解部分最优解
四、动态规划的递归和迭代法求解
一由顶向下的递归法
由顶向下的递归法也被称为带记忆的由顶向下法可概括为递归可记忆是一种自上而下的分治思想一开始将问题分成子问题通过递归先解决子问题这里的可记忆指的是保存每个子问题的解这些解被保存到一个数组或表格中其目的是为了避免重复计算节省时间。该方法通常由递归函数实现同时结合记忆化可以消除重复计算从而大幅度提升计算效率缩短时间。
二由底向上的迭代法
由底向上的迭代方法可概括为迭代动态规划是一种自下而上的构建思想。通过将问题分成相互独立、可简单直接求解的子问题并将子问题的解按由小到大的顺序保存下来逐步构建出问题的最优解即当求解某个子问题时其所依赖的更小的子问题已经是求解了的从而每个子问题只需求解一次即可。该方法通常由循环语句实现可以避免采用递归函数时所带来的额外开销。 以上两种方法具有相同的渐进运行时间仅有的差异是在某些特殊情况下由顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销由底向上方法的时间复杂性函数通常具有更小的系数。 五、动态规划的应用
一斐波那契数列
由斐波那契数列Fibonacci可得
递归关系式F(n) F(n-1) F(n-2)
其中F(0)0F(1) F(2) 1。f(n)的求解可以类比一棵二叉树以F(5)为例根据递归关系式可画出二叉树如下图 1、若采用不带记忆的由顶向下的递归法时其中有重复的子问题会造成重复计算从而加大开销且当计算的n值越来越大时空间开销会更大。 所以采用带记忆的由顶向下的递归法通过建立一个一维数组来保存每个子问题的解当计算时只需从数组中取出相应的值即可从而可以避免重复计算【避免子问题重叠】。这种方法只需求需要的相应值即可该树中有重复的子问题如下 创建一个数组首先将F(0)、F(1)和F(2)的解存在数组中如下
F(0)F(1)F(2)数组011
求解F(3)时根据递归关系式F(n) F(n-1) F(n-2) 即F(3) F(2) F(1) 112直接取数组中F(2)和F(1)的值代入计算即可然后将F(3)存放在数组中如下
F(0)F(1)F(2)F(3)数组0112
求解F(4)时根据递归关系式F(n) F(n-1) F(n-2) 即F(4) F(3) F(2) 213直接取数组中F(3)和F(2)的值代入计算即可然后将F(4)存放在数组中如下
F(0)F(1)F(2)F(3)F(4)数组01123
……依次最终求得F(5)F(4) F(3)325
F(0)F(1)F(2)F(3)F(4)F(5)数组011235
2、若采用由底向上的迭代方法自下而上的构建通常由循环语句实现可以避免采用递归函数时所带来的额外开销如下代码通过for()循环实现
#include stdio.h
int main()
{int i, n;long long int f1 1, f2 1, f; //初始值f1f21printf(请输入要输出的斐波那契数列项数);scanf(%d, n);printf(斐波那契数列前%d项为\n, n);printf(%lld %lld , f1, f2);for (i 3; i n; i){f f1 f2;printf(%lld , f);f1 f2;f2 f;}printf(\n);return 0;
}二汉诺塔
首先这里简单地以一个三层的汉诺塔熟悉一下汉诺塔的游戏规则一共有三根柱子第一根柱子上有三个从上到下由小到大的圆盘规定每次在三根柱子之间一次只能移动一个圆盘且小圆盘上不能放大圆盘试将第一根的三个圆盘移动到第三根柱子上。 点击链接可以试试怎么让移动的次数最少 汉诺塔可视化小游戏 Tower of Hanoi 最终的目的是完成的步数越少越好我们可以很容易地得到三层的汉诺塔的最少移动步数为7次移动过程中三个柱子共有8种不同的状态如下 同样的四层的汉诺塔的最少移动步数为15次而移动过程中三个柱子共有16种不同的状态 五层的汉诺塔的最少移动步数为31次而移动过程中三个柱子共有32种不同的状态 …… 通过数学归纳法可得当汉诺塔的层数为n时最少的移动次数为 2n-1次移动过程中三个柱子共有2n 种不同的状态其时间复杂度为O(2n) 。
汉诺塔问题的动态规划优化问题是通过带记忆的由顶向下法求解即递归可记忆先解决小的问题然后将问题的规模从小到大逐步扩大最终得到问题的答案且过程中避免了重复计算。【避免子问题重叠】 若以f[ n ]表示n个圆盘从TOWER 1移动到TOWER 3的最少步数则f[1] 1即一个圆盘移动到TOWER 3的步数为1而当n1时分析可知 为了符合规则需要先将一部分移动到TOWER 2上面即有n-1个圆盘从TOWER 1经TOWER 3移动到TOWER 2上面然后再将最大的圆盘移动到TOWER 3上面由于TOWER 2已经是有序的所以需要将这n-1个圆盘从TOWER 2移动到TOWER 1最终再移动到TOWER 3上。 可得n个圆盘从TOWER 1移动到TOWER 3的最少步数为f[ n ]f (n -1) 1 f (n - 1)2f (n - 1)1 2n-11即T(n) 2n-11所以时间复杂度为O(2n) 。 也可以从圆盘的数量来计算按照规则一个圆盘从TOWER 1移动到TOWER 3需要1步两个圆盘从TOWER 1移动到TOWER 3需要3步小的圆盘移动到中转点再将大的圆盘移动到终点最后将小的圆盘移动到终点三个圆盘从TOWER 1移动到TOWER 3需要7步……n个圆盘从TOWER 1移动到TOWER 3需要3步 2n-1步。 三最优二叉查找树
1、最优二叉查找树的定义 在n个不同关键字组成的有序序列中每个关键字被查找的概率为pi通过关键字构造一棵的二叉查找树它具有最小平均比较次数即为最优二叉查找树OBST且左右子树也是最优二叉查找树但最优二叉查找树不一定是高度最小的二叉查找树。 2、二叉查找树平均比较次数的计算 设有n6个关键字的集合各个实结点的查找概率分别为55%、230%、910%、03%、414%、625%假设虚结点的查找概率分别为e02%、e110%、e25%、e35%、e411%、e515%、e610%计算二叉查找树的平均比较次数 实结点1×0.052×0.30.13×0.030.140.252.11 虚结点2×0.023×0.10.050.050.110.150.11.72 即二叉查找树的平均比较次数为2.111.723.83。 3、最优子结构 最优二叉查找树中采用了动态规划的思想分析其最优子结构若一个二叉查找树是最优二叉查找树可将其分为根结点、左子树和右子树所以其左、右子树也是最优二叉查找树。 4、构建最优二叉查找树的分析 构建一个含n个关键字的最优二叉查找树的时间复杂度为O(n3)由于通过使用二维数组避免重复计算子树的最小权值和【避免子问题重叠】从而提高了算法的效率其空间复杂度为O(n2)。
四矩阵连乘
问题描述在《线性代数》里面学过矩阵的乘法若干个矩阵相乘时由于满足结合律即(AB)C A (BC)可以通过加括号可以改变乘积的顺序而结果不改变。若从相乘的计算量上来看怎么让计算所需要的代价最少即怎么通过加括号改变乘积顺序来使计算量最小这是通过动态规划来优化问题的所在。
可将问题划分成两个子问题即两个部分的矩阵相乘分别对两个子问题进行递归求解通过定义一个二维数组C[i][j]来表示第i个矩阵到第j个矩阵相乘的最小代价以分界点k分割问题对于两个子问题可分别表示为C[i][k]和C[k1][j]然后通过相同的方法继续进行递归求解由于第i个矩阵的行数在p[i-1]其列数在p[i]所以递归式为C[i][j]C[i][k]C[k1][j]p[i-1]×p[k]×p[j]该算法的时间复杂度取决于对所有矩阵求优解即递归式上花费的时间时间复杂度为O(n3)。
五0-1背包
问题描述有n件物品对某一物品i其价值为V重量为W怎么选择将物品放入背包中使得放入背包的物品的总价值最大而动态规划就是来优化这个问题。
通过一个数组C[i][j]表示i个物品放入背包此时背包容量为j所能得到的最大价值由于当每个物品放入背包时都要两种情况能放进背包的要求是其所占重量要小于或等于当前背包剩余容量即此时总价值为C[i-1][j-wi]vi不能放进背包的情况时此时总价值为C[i-1][j]然后通过这两种状态取最大值即C[i][j]Max{C[i-1][j]C[i-1][j-wi]vi}。由于得到的是背包的最大价值设in、jW再通过一开始的最优解C[n][W]的值反推确定放入背包的相应物品即实现放入背包物品价值最大化该算法的时间复杂度取决于物品个数n的一个for()循环语句和物品的重量W的一个for()循环语句故其时间复杂度为O(nW)。
