动态规划(Dynamic programming)

动态规划本质上是将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。核心是避免不必要的计算，尽量缩小可能解空间, 主要操作是寻找递推公式。

假设你正在爬楼梯。需要 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 阶

先看动态规划法：

接下来，我们用f(n)来表示爬到第N级台阶所有的方法数。那么爬到第N级台阶有几种方法呢？答案是两种，从N-2层一次爬两级到达第N层，从第N-1层一次爬一级到达第N层。也就是说f(n)的值只和f(n-1),f(n-2)相关 准确的说是爬到第N级的方法数就是爬到第N-2层和第N-1层的方法数之和。即

f(n) = f(n-1) + f(n-2)

f(1) = 1 ，f(2) = ，f(n) = f(n-1) + f(n-2)。由此就可以根据递推公式计算出到达所有的台阶的方法数。

时间复杂度On，空间复杂度On。

我们再来看暴力解法：
在暴力法中，我们将会把所有可能爬的阶数进行组合，也就是 1 和 2 。如果第一次爬一级，接下来就需要计算爬四级台阶的组合数，如果第二次又爬一级接下来就需要计算爬三级的组合数。如果第一次爬两级，接下来就又需要计算爬三级的组合数。这里其实就产生了重复计算。简图如下：

       5
    /     \
  4         3
 / \       / \
3   2     2   1

我们再来看下动态规划的基本内容：

动态规划本质上是将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解(将爬N级台阶的问题分解成爬N-2级台阶。和N-1级台阶的问题)。核心是避免不必要的计算，尽量缩小可能解空间(减少了对重复组合数的计算，例如暴力法中就计算了两次3的组合数), 主要操作是寻找递推公式(f(n)的值只和f(n-1),f(n-2)相关准确的说是 f(n) = f(n-1) + f(n-2))。

到此，动态规划的问题算是理解完毕，详解参考[引用 & 参考](# 引用 & 参考)1,2

引用 & 参考

https://www.zhihu.com/question/23995189/answer/613096905
https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/