成化区建设局网站,直接进网站的浏览器,微赞直播平台,各种颜色做网站给人的心里暗示动态规划需要弄清楚两个问题#xff0c;首先子问题的最优解#xff0c;其次重叠子问题。首先来看一个问题吧#xff1a; 有3种硬币#xff0c;对应的面值是1、2、4#xff0c;如果要组成11元#xff0c;最少需要几枚硬币呢#xff1f; 思路#xff1a;考虑组成0元… 动态规划需要弄清楚两个问题首先子问题的最优解其次重叠子问题。首先来看一个问题吧 有3种硬币对应的面值是1、2、4如果要组成11元最少需要几枚硬币呢 思路考虑组成0元需要0枚硬币f(0) 0。这里设f(n)为组成n元最少需要的硬币数; 考虑组成1元需要1枚硬币f(1) 1; 考虑组成2元可以有f(2) min (f(1) 1, f(0) 1) f(0) 1 1; 考虑组成3元可以有f(3) min (f(2) 1, f(1) 1) f(1) 1 2; 可以看出f(n)依赖于f(i),f(j),,,等等其中i,j都小于n也就是说f(n)的解包含了子问题的最优解。另外在解f(1)、f(2),,,f(n)过程中子问题的解被重复的利用到。 我们可以写出该问题的最优子结构d(i)min{ d(i-vj)1 }其中i-vj 0vj表示第j个硬币的面。 现在可以了解下动态规划的一些概念。用动态规划求解问题的第一步就是描述最优解结构。考虑最优子结构先考虑两个方面1 有多少个子问题被使用在原问题的一个最优解中以及2在决定一个最优解中使用哪些子问题时有多少个选择。这其中第二个问题也是描述最优子结构的关键上面的例子中考虑11元的最优解时使用哪些子问题便有3个选择。除了最优子结构外使用于动态规划仍需满足重叠子问题也就说可以用递归的算法反复的求解同样的子问题而不是总产生新的问题。动态规划算法每个子问题只解一次把解保存在一个在需要时就可以查看的表中而没错查询表的时间为常数。另外动态规划算法是自底向上来求解由上面的例子可以看出求f(11)时需要的子问题的值已计算过了。 动态规划算法的时间复杂度也是需要考虑的一般来说算法的时间复杂度依赖两个因素1求最优解时需要考虑的选择的个数2总共有多少个子问题。上面的例子有O(n)个子问题且有三个选择来检查每个子问题则时间复杂度是O(n)。 使用动态规划求解的问题也是较多典型的例子有 01背包问题 LCS最长公共子序列问题 有向无环图的最短路径问题带权不带权值的可以用深度/广度优先遍历来求 分析待以后再补充。 转载于:https://www.cnblogs.com/xiaer/p/5237925.html
