动态规划-爬楼梯.md

title	date	categories	tags
动态规划：爬楼梯	2022/07/25	数据结构与算法 动态规划	动态规划

注意

GitHub 的 Markdown 渲染功能不足，文章的完整渲染欢迎来我的 博客小站 查看~~

题目描述

思路与题解

;;;id1 思路 n 阶，可以看成是 n-2 阶爬 2 阶后到达，也可以看成是 n-1 阶爬 1 阶后到达，所以就是 n-2 阶的爬取数 + n-1 阶的爬取数，翻译过来就是斐波那契数，easy~ ;;;

;;;id1 我的题解

class Solution {
public:
    int climbStairs(int n) {
        // n 阶，可以看成是 n-2 阶爬 2 阶后到达
        // 也可以看成是 n-1 阶爬 1 阶后到达
        // 所以就是 n-2 阶的爬取数 + n-1 阶的爬取数
        // 翻译过来就是斐波那契数，easy
        if (n < 4) return n;
        int p = 0, q = 2, r = 3;
        for (int i = 4; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};

;;;