qq_50982664的博客

原创 动态规划

动态规划 解题思想 将给定问题分解成子问题，通过求解子问题得出原问题的解，即自底向上。 适用情况 有重叠子问题：用递归自顶向下对问题求解时，有些子问题会被重复计算多次。 有最优子结构：问题的最优解所包含的子问题的解也是最优的。 后无效性：子问题的解一旦确定就不再改变。 自顶向下 VS 自底向上 实例：斐波那契数列 将斐波那契数用F(n)表示，该数列由0和1开始，后面的每一项数字都是前面两项数字的和，即： F(0)=0, F(1)=1 F(n)=F(n-1)+F(n-2), 其中n>1 给定n，计