零一背包问题探究动态规划

「重叠子问题：比如斐波那契数列中的f(5)，算了f(4)和f(3)，结果f(4)又给Runsen算了一次f(3)。其实就是将一棵二叉树进行剪枝操作，方法是备忘录来存储在内存上。」

「自下而上：反过来求解」

动态规划思路

动态规划是一种求问题最优解的方法。通用的思路：将问题的解转化成==> 求解子问题，==> 递推，==>最小子问题为可直接获得的初始状态。

详细的步骤下面所示：

判断是否可用递归来解，可以的话进入步骤 2

分析在递归的过程中是否存在大量的重复子问题

采用备忘录的方式来存子问题的解以避免大量的重复计算(剪枝)

改用自底向上的方式来递推，即动态规划

关键就是「找状态转移方程」。

斐波那契数列和爬楼梯问题

斐波那契数列最早从兔子问题演变过来的，

假设一对初生兔子一个月到成熟期，一对成熟兔子每月生一对兔子，并且一年内没有发生死亡。那么，由一对初生兔子开始 一年以后可以繁殖多少对兔子?

 

现以上规律是，每月的兔子对数=上一月的兔子对数+该月新生的兔子对数=上一月的兔子对数+上上月的兔子对数

得到序列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

这个序列即为斐波那契数列“(Fibonacci sequence)”。斐波那契数列中的任一个数，都叫斐波那契数

斐波那契数列，通常都是用来讲解递归函数，尝试用递归的思路来解决，但是时间复杂度高达

（编辑：鹤壁站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!