动态规划--简单题型之爬楼梯

爬楼梯

假设你需要爬 n 个台阶才能到达楼顶，每次你可以爬 1 或 2 个台阶，那么有多少种不同的方法才能爬到楼顶呢 ?

分析

定义数组 dp[i] ,表示爬到第i层楼有 dp[i] 种方法。

数组dp[i] 从两个方向推导出来的：

1. dp[i-1]，上i-1层楼梯有dp[i-1]种方法，下一步上一个台阶就是dp[i]；

2. dp[i-2], 上i-2层楼梯有dp[i-2]种方法，下一步上两个台阶就是dp[i]；

即dp[i] = dp[i-1]+dp[i-2]

代码实现

#include<iostream>
using namespace std;
class Solution {
    
	public:
		int ClimbStairs(int n) {
    
			int dp[3];
			dp[1] = 1;
			dp[2] = 2;
			if (n < 3) return dp[n];
			for (int i = 3; i <= n; i++) {
    
				int sum = dp[1] + dp[2];
				dp[1] = dp[2];
				dp[2] = sum;
			}
			return dp[2];
		}	
};
int main() {
    
	Solution Q;
	int n;
	cin>>n;
	cout<<Q.ClimbStairs(n);
}