如题（基础题）：

经典的爬楼梯问题，先从递归想起；

class Solution {
public:int climbStairs(int n) {if(n==1)return 1;if(n==2)return 2;return climbStairs(n-1)+climbStairs(n-2);}
};

之后可以想办法（如哈希表）去降低时间复杂度，即记忆化搜索或递归树的剪枝，避免对已经计算过的结点再次计算；

class Solution {
public:int climbStairs(int n) {int* memo=new int[n+1];return climbStairsMemo(n,memo);}int climbStairsMemo(int n,int memo[]){if(memo[n]>0){return memo[n];}if(n==1)memo[n]=1;else if(n==2)memo[n]=2;else{memo[n]=climbStairsMemo(n-1,memo)+climbStairsMemo(n-2,memo);}return memo[n];}};

既然都有递归了，那肯定有非递归的解法（比如从n=1或n=2进行逆运算）；

class Solution {
public:int climbStairs(int n) {if(n==1){return 1;}int* dp=new int[n+1];dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};

扩展：斐波那契数列；

同上：

斐波那契数列的每一项是前两项之和，通常从 0 和 1 开始。用数学公式表示为：

F(n)=F(n−1)+F(n−2)

扩展：

递归：

class Solution {
public:int dfs(int n,vector<int>& cost){if(n<=1){return 0;}return min(dfs(n-1,cost)+cost[n-1],dfs(n-2,cost)+cost[n-2]);}int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();return dfs(n,cost);}
};//一般都超时

剪枝：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();vector<int> memo(n+1,-1);function<int(int)> dfs=[&](int i)->int{if(memo[n]!=-1){return memo[n];}if(n<=1){return 0;}return memo[n]=min(dfs(n-1)+cost[n-1],dfs(n-2)+cost[n-2]);};return dfs(n);}
};

递推：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();vector<int> dp(n+1);if(n<=1){dp[n]=0;}for(int i=2;i<=n;i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
};