本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

爬楼梯

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

二、思路分析

• 不知不觉已经刷了不少leetcode了。今天来看看一篇有意思的leetcode–爬楼梯。
• 对于 儿童来说正常最多可以迈出两步台阶至少一步台阶。我们就以这个为前提来生活化本题。
• 既然是迈台阶那么就有一个起点到终点的问题，上学期间经常听老师说做人要脚踏实地、实事求是。我们想要到达终点就得一步一步的往上爬。
• 换句话说终点状态是由开始状态一步一步转变的。既然是一步一步那么正好和我们的动归理论吻合。所以爬楼梯就是动态规划的考点

转移方程

• 动态规划为什么我每次都是先讲转移方程呢？因为他是动归的起点。也是最重要的环节。这里说的起点并不是初始值的意思。而是说他是动态规划整个功能的核心部分。没有他就无法进行运转下去。
• 回到本题我们假设F(x)表示从第一个台阶到第x个台阶的走法个数。从某个台阶我们可迈出一步也可以迈出两步。

• 从上图我们可以得知，F(x)可以由F(x-1)跨一步走过来所以包含了F(x-1);另外也可以有F(x-2)走两步过来。所以得出如下方程