前端之算法（七）动态规划

大家好，今天我们要聊的是动态规划这种方法，它和分而治之一样，也是算法设计中的一种方法，你同样可以把它当作解决问题的一种思路。接下来让我来看看动态规划是什么？

动态规划

• 动态规划是算法设计中地一种方法。

• 它将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题。

• 看到这，你会发现它分而治之是一样的。其实不然，分而治之，是把问题分解成相互独立的子问题，而动态规划是把问题分解成相互重叠的子问题。

那什么是相互重叠呢？

可以给大家举一个很典型的列子。

• 斐波那契数列

从第三个数开始，所有值都等于它前个两个值之和。

那怎么解决斐波那契数列呢？

这个时候就要用到动态规划了。

• 定义子问题：F(n) = F(n - 1) + F(n - 2)

• 反复执行：从 2 循环到 n，执行上述公式。

这时候我们发现每个子问题都是一套公式，通过这套公式反复求解，这就是相互重叠的。

LeetCode：70.爬楼梯

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

注意：给定 n 是一个正整数。

示例 1：
输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1.  1 阶 + 1 阶2.  2 阶
示例 2：
输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1.  1 阶 + 1 阶 + 1 阶2.  1 阶 + 2 阶3.  2 阶 + 1 阶

解题思路

• 爬到第 n 阶可以在第 n - 1 阶爬一个台阶，或者在第 n - 2 阶爬 2 个台阶。

• F(n) = F(n - 1) + F(n - 2)

function climbStairs(n: number): number {    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]};

End~