【前言】
今天是刷题打卡第53天！
加油啦各位。
原题：爬楼梯（记忆化搜索、简单DP）
题目描述：
示例1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
首先分析一下本题：
注意：注意这个题目问的是什么？
问的不是能爬多少次，而是有多少种方法能到最后一个台阶。
问题分析：当n > 2时，第一次爬就有两种不同的选择：一是第一次只爬一级，此时爬法数目等于后面剩下的（n - 1）级台阶的爬法数目，即为f(n - 1); 还有一种选择是第一次爬两级，此时爬法数目等于后面剩下的（n - 2）级台阶的爬法数目，即为f(n - 2).
所以有：f(n) = f(n - 1) + f(n - 2)
当n == 1时，有1种爬法；
当n == 2时，有2种爬法；
当n == 3时，有3种爬法；
当n == 4时，有5种爬法。
是呀，这题跟斐波那契数列基本上一样，不过这道题目需要思考一下，没有斐波那契这么明显。但是需要注意的是，递归边界还是有所不同的哦！
方法一：暴力递归
代码执行：
class Solution { public: int climbStairs(int n) { //方法一：暴力递归 //找边界 if(n == 1){ return 1; } if(n == 2){ return 2; } return climbStairs(n - 1) + climbStairs(n - 2); } };
方法二：记忆化搜索（简单DP）
代码执行：
class Solution { public: int climbStairs(int n) { //方法二:记忆化搜索（简单DP） //找边界 if(n == 1){ return 1; } if(n == 2){ return 2; } //定义一个大小为n+1的整型数组，并且初始化为0 vector<int> dp(n+1, 0); dp[1] = 1; dp[2] = 2; for(int i = 3; i < n+1; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } };
结语
今天是刷题打卡第53天！
加油吧少年。
