[每日一题]DP小结一：重叠子问题

如下是我关于 动态规划 的理解，有理解不到位的地方欢迎指正！一起讨论，争取大家一起攻克动态规划的难题。

今天的题目是 70. Climbing Stairs

You are climbing a stair case. It takes

You are climbing a stair case. It takes n steps to reach to the top.

https://leetcode.com/problems/climbing-stairs/#/description

这道题其实是一道求 斐波拉契数列的题。斐波拉契数列是动态规划的经典题，题目不难但可以考察到动态规划的很多方面。所以非常适合通过斐波拉契数列来理解动态规划。

动态规划思想是将一个复杂的问题转换成多个子问题，并且存储子问题的处理结果。

一般情况下，我们求最优解都是遍历所有的可行方案，最后选择最符合要求的结果。但当数据量比较大的时候，穷举方案不可行。这个时候，就需要考虑使用动态规划来解决这类问题。

动态规划有如下几个特性：

1. 有重叠的子问题

2. 具有最优子结构

3. 无后效性