Dynamic programming -- simple question type of climbing stairs

climb stairs

Suppose you need to climb n It takes steps to reach the roof , Every time you climb 1 or 2 A stair , So how many different ways can you climb to the roof ?

analysis

Define an array dp[i] , It means to climb to the first i The first floor has dp[i] Methods .

Array dp[i] Derived from two directions ：

1. dp[i-1], On i-1 Stairs on the first floor dp[i-1] Methods , The next step is dp[i];

2. dp[i-2], On i-2 Stairs on the first floor dp[i-2] Methods , The next two steps are dp[i];

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

Code implementation

#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);
}