动态规划（dp）- 爬楼梯

前言

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

斐波那契数列

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

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

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

暴力法

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

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的对象来缓存计算的结果，示例如下：

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）是一种解决多阶段决策问题的数学算法。它通过将复杂问题分解为更简单的子问题，并利用子问题的解来构建原问题的解。

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

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

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

基本步骤

设计状态
确定状态转移方程
确定初始状态
执行状态转移
计算最终的解

爬楼梯

leetcode-70 简单

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

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

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

下面用javascript代码实现一下：

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)。

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代码实现

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
}