白筱汐

想都是问题,做都是答案

0%

动态规划(dp)- 爬楼梯

前言

学习动态规划之前,我们先来了解一下斐波那契数列。通过解决这个问题,慢慢我们就学会了动态规划的思想。

斐波那契数列

斐波那契数列是一个经典的数学问题,它的定义是:前两个数字是 0 和 1,之后的每个数字都是前两个数字之和。

因此,斐波那契数列的前几个数字依次是:0、1、1、2、3、5、8、13、21、34,以此类推。

这里就涉及到状态转移了,对于数组,从它的第3项开始满足,f(2) = f(n-1) + f(n - 2)。

暴力法

可以通过暴力法递归实现相关代码:

1
2
3
4
5
6
7
8
9
function fib(n) {
if (n === 0) {
return 0
} else if (n === 1) {
return 1
} else {
return fib(n - 1) + fib(n - 2)
}
}

这个方法的性能很差,因为它存在许多重复的递归,它的时间复杂度为O(2^n)。为了减少这些重复计算,需要对计算结果进行缓存。

记忆化搜素

记忆化搜素与暴力法相比,就是多了一个缓存体,记录了子问题的计算结果。我们整个分解问题,成为一个个的子问题。然后找到计算过的子问题的结果进行汇总,最后得到了整个问题的答案。

通常我们使用hash缓存结果,在javascript中对象就是一种hash结构。我们利用javascript的对象来缓存计算的结果,示例如下:

1
2
3
4
5
6
7
8
9
10
function fib(n) {
if (fib.cache[n]) {
return fib.cache[n]
}
return fib.cache[n] = fib(n - 1) + fib(n -2)
}
fib.cache = {
0:1,
1:1
}

记忆化搜索的效率已经和动态规划一样了。实际上这种解法和动态规划的思想已经差不多了。只不过记忆化搜索是自顶向下(从结果往子问题推导),动态规划是自底向上(从子问题往结果推导)。

动态规划

动态规划(Dynamic Programming,简称dp)是一种解决多阶段决策问题的数学算法。它通过将复杂问题分解为更简单的子问题,并利用子问题的解来构建原问题的解。

动态规划通常适用于具有重叠子问题和最优子结构性质的问题。其中,重叠子问题表示在解决问题的过程中会多次遇到相同的子问题,而最优子结构表示问题的最优解可以由其子问题的最优解构成。

动态规划的基本思想是将原问题分解为若干个子问题,并按照一定的顺序求解子问题,将子问题的解保存下来,避免重复计算。最终,通过求解子问题得到原问题的解。

在使用动态规划时,一般采用自底向上的方式进行计算。即从最小的子问题开始解决,逐步构建出更大规模的子问题的解,直至解决整个原问题。

基本步骤

  1. 设计状态
  2. 确定状态转移方程
  3. 确定初始状态
  4. 执行状态转移
  5. 计算最终的解

爬楼梯

leetcode-70 简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

这个问题其实和斐波那契数列类似,它的状态转移方式是一样的,f(n) = f(n - 1) + f(n -2)。

但是它的初始状态有所不同,f(0) = 1,f(1) = 1。

下面用javascript代码实现一下:

1
2
3
4
5
6
7
8
function climbStairs(n) {
if (n < 2) return 1
const dp = [1,1]
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i -2]
}
return dp[n]
}

我们可以使用滚动数组思想把空间复杂度优化成O(1)。

1
2
3
4
5
6
7
8
9
10
11
function climbStairs2(n) {
if (n < 2) return 1
let p = 1,q = 1
for (let i = 2; i <= n; i++) {
// 通过一个临时变量来转移状态,优化空间复杂度
const temp = p
p = q
q = temp + q
}
return q
}

go代码实现

1
2
3
4
5
6
7
8
9
10
func climbStairs(n int) int {
if n < 2 {
return 1
}
p, q := 1, 1
for i := 2; i <= n; i++ {
p, q = q, p+q
}
return q
}