leetcode | 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?

    解析：

    本题是个动态规划问题，最优解可有子问题的的最优解组成，具有重复的子问题，

leetcode | Climbing Stairs

    由题目可知要求到达第n阶台阶的所有方法f(n)，又每次能登1~2个台阶，

    - 从 n-1 阶登 1 步 到达 n 阶

    - 从 n-2 阶登 2 步 到达 n 阶

    因此f(n)=f(n?1)+f(n?2)费波那也数列

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

电脑资料

<code class="hljs vala">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;    }};</code>