leetcode | Climbing Stairs

Climbing Stairs : https://leetcode.com/problems/climbing-stairs/

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

解析：
本题是个动态规划问题，最优解可有子问题的的最优解组成，具有重复的子问题。
由题目可知要求到达第n阶台阶的所有方法f(n)，又每次能登1~2个台阶，
- 从 n-1 阶登 1 步 到达 n 阶
- 从 n-2 阶登 2 步 到达 n 阶
因此 $f(n) = f(n-1) + f(n-2)$ 费波那也数列

难点在于想到递归式，对于递归问题注意从后往前看。

class Solution {
    
public:// f(n) = f(n-1)+f(n-2)int climbStairs(int n) {int prev = 0;int cur = 1;for(int i = 1; i <= n; i++) {int temp = cur;cur += prev;prev = temp;}return cur;}
};