前言
学习动态规划之前,我们先来了解一下斐波那契数列。通过解决这个问题,慢慢我们就学会了动态规划的思想。
斐波那契数列
斐波那契数列是一个经典的数学问题,它的定义是:前两个数字是 0 和 1,之后的每个数字都是前两个数字之和。
因此,斐波那契数列的前几个数字依次是:0、1、1、2、3、5、8、13、21、34,以此类推。
这里就涉及到状态转移了,对于数组,从它的第3项开始满足,f(2) = f(n-1) + f(n - 2)。
暴力法
可以通过暴力法递归实现相关代码:
1 | function fib(n) { |
这个方法的性能很差,因为它存在许多重复的递归,它的时间复杂度为O(2^n)。为了减少这些重复计算,需要对计算结果进行缓存。
记忆化搜素
记忆化搜素与暴力法相比,就是多了一个缓存体,记录了子问题的计算结果。我们整个分解问题,成为一个个的子问题。然后找到计算过的子问题的结果进行汇总,最后得到了整个问题的答案。
通常我们使用hash缓存结果,在javascript中对象就是一种hash结构。我们利用javascript的对象来缓存计算的结果,示例如下:
1 | function fib(n) { |
记忆化搜索的效率已经和动态规划一样了。实际上这种解法和动态规划的思想已经差不多了。只不过记忆化搜索是自顶向下(从结果往子问题推导),动态规划是自底向上(从子问题往结果推导)。
动态规划
动态规划(Dynamic Programming,简称dp)是一种解决多阶段决策问题的数学算法。它通过将复杂问题分解为更简单的子问题,并利用子问题的解来构建原问题的解。
动态规划通常适用于具有重叠子问题和最优子结构性质的问题。其中,重叠子问题表示在解决问题的过程中会多次遇到相同的子问题,而最优子结构表示问题的最优解可以由其子问题的最优解构成。
动态规划的基本思想是将原问题分解为若干个子问题,并按照一定的顺序求解子问题,将子问题的解保存下来,避免重复计算。最终,通过求解子问题得到原问题的解。
在使用动态规划时,一般采用自底向上的方式进行计算。即从最小的子问题开始解决,逐步构建出更大规模的子问题的解,直至解决整个原问题。
基本步骤
- 设计状态
- 确定状态转移方程
- 确定初始状态
- 执行状态转移
- 计算最终的解
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
这个问题其实和斐波那契数列类似,它的状态转移方式是一样的,f(n) = f(n - 1) + f(n -2)。
但是它的初始状态有所不同,f(0) = 1,f(1) = 1。
下面用javascript代码实现一下:
1 | function climbStairs(n) { |
我们可以使用滚动数组思想把空间复杂度优化成O(1)。
1 | function climbStairs2(n) { |
go代码实现
1 | func climbStairs(n int) int { |