动态规划 -- 3




200x200


问题一大早,前同事在微信上给出了个题:一只青蛙上台阶,一次只能上一个或两个台阶,如果总共有3个台阶,那么有三种上法:111 -- 每次上一个台阶21 -- 先上

#技术帖    #算法    #python    #动态规划   

200x200


概述最长公共子序列是很多领域的经典问题,其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最

#读书笔记    #技术帖    #算法    #算法导论   
最优子结构动态规划算法最大的特性是:局部最优中产生整体最优。具体方法是:逐层迭代,从局部开始,一步一步走到整体。用动态规划求解最优化问题的第一步是描述最优解的结构,如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子结构当一个问题具有最优子结构时,我们才可以在分治法、动态规划、贪心策略等算法中进行选择在动态规划中,我们利用子问题的最优解来构造问题的一个最优解 寻找最优子结构时,可以遵循一种共同的模式:问题的一个解可以是做一个选择,如选择一个前一个装配站或者选择一个下标以在该位置分裂矩阵,选择完成后会得到一个或多个子问题假设对一个给定的问题,一直的是一个可以导致最优解的选择,我们不必去关系如何确定这个选择,只要假定它是已知的(与数学上的归纳证明方法是类似的)在已知这个选择后,要确定那些子问题会随之发生,以及如何最好的描述所得到的子问题空间利用一个“剪贴”(cut-and-paste)的技术,来证明在问题的一个最优解中,使用的子问题的解本身也必须是最优的,通过假设一个子问题的解都 不是最优解然后导出矛盾即可 动态规划以自底向上的方式来利用最优子结构,也就是说,首先找到子问题的最优解,解决子问题,然后找到问题的一个最优解,寻找问题的最优解需要在子问题中作出选择,即选择将用哪一个来求解问题 重叠子问题适用于动态规划方法求解的问题必须具有的第
#读书笔记    #技术帖    #算法    #算法导论   



京ICP备15018585号