Introduction

70. Climbing stairs

To solve this problem, we need to introduce a new algorithm called dynamic programming.

为了解决leetcode中的第70题，我们需要先介绍动态规划。 我们先看题目： You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 有两种方法进行思考 方法一（自顶向下）： 想要知道到达n有多少种方法，有两种情况，情况一：通过从n-1层台阶向上走一格到达，或者情况二：从n-2层台阶向上走两个到达。 注意这里只有这两种情况，因为从n-2层台阶向上走一个就会到达n-1层，也就变成了第一种情况。 因此我们只需要知道到达n-1和n-2的方法数总和即可，因为从n-1或n-2到达n均只有一种走法，不会让走法变多。 这样我们就可以通过