企业官网建设流程全解析

看上去高端的网站,网址你懂我意思吧在线2021,云伙伴小程序开发公司,园林工程建设网站【LeetCode 70】爬楼梯#xff08;C#xff09;解题思路与代码实现在LeetCode的算法题中#xff0c;爬楼梯是一道经典的入门动态规划题目#xff0c;其核心思想是通过递推关系找到问题的解。本文将详细讲解这道题的解题思路#xff0c;并给出C的实现代码#xff0c;同时分…【LeetCode 70】爬楼梯C解题思路与代码实现在LeetCode的算法题中爬楼梯是一道经典的入门动态规划题目其核心思想是通过递推关系找到问题的解。本文将详细讲解这道题的解题思路并给出C的实现代码同时分析不同解法的优劣。一、题目描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢提示 1 n 45示例- 输入 n 2 输出 2 1阶1阶、2阶- 输入 n 3 输出 3 111、12、21二、解题思路这道题的核心是找到递推公式我们可以通过分析小规模的情况推导规律1. 当 n 1 时只有1种方法爬1阶2. 当 n 2 时有2种方法11、23. 当 n 3 时到达第3阶的最后一步只能是从第2阶爬1阶或从第1阶爬2阶因此方法数为 f(2) f(1) 3 4. 以此类推对于第 n 阶方法数 f(n) f(n-1) f(n-2) 。这本质上是斐波那契数列的应用只是初始条件略有不同斐波那契数列通常以 f(0)0, f(1)1 开头本题 f(1)1, f(2)2 。解法选择- 递归直接按递推公式递归但会存在大量重复计算时间复杂度为 O(2^n) 当 n45 时会超时- 动态规划迭代用变量保存中间结果避免重复计算时间复杂度 O(n) 空间复杂度 O(1) 是本题的最优解。三、C代码实现这里采用迭代法实现仅用三个变量保存中间值空间复杂度优化至 O(1) cppclass Solution {public:int climbStairs(int n) {// 处理边界情况n1返回1n2返回2if (n 2) {return n;}// a表示f(n-2)b表示f(n-1)c表示f(n)int a 1, b 2, c 0;// 从第3阶开始迭代计算到第n阶for (int i 3; i n; i) {c a b; // 计算当前阶的方法数a b; // 递推a变为下一次的f(n-2)b c; // 递推b变为下一次的f(n-1)}return c;}};代码解释1. 边界处理当 n≤2 时直接返回 n 因为这两种情况的方法数是确定的2. 变量初始化 a 初始为 f(1)1 b 初始为 f(2)2 c 用于存储当前阶的方法数3. 迭代计算从第3阶开始依次计算每一阶的方法数通过递推更新 a 和 b 最终 c 即为 f(n) 。四、测试用例验证我们可以通过几个测试用例验证代码的正确性1. 输入 n1 输出 1 符合预期2. 输入 n2 输出 2 符合预期3. 输入 n3 输出 3 符合预期4. 输入 n5 输出 8 方法11111、1112、1121、1211、2111、122、212、221。五、总结爬楼梯问题是动态规划的入门经典题其核心是找到递推关系并通过迭代优化时间和空间复杂度。本题的迭代解法将时间复杂度控制在 O(n) 空间复杂度优化至 O(1) 能够高效处理题目给定的 n≤45 的范围。对于这类递推型问题我们需要先通过小规模案例推导规律再选择合适的解法递归/迭代/动态规划同时注意优化重复计算和空间占用