序言

算法

算法是一种良好的解决问题流程，程序从接收到输入值经过处理得到明确的输出，在计算机科学领域追求将程序逻辑以更高效的方式处理事务。虽然单个程序的执行消耗可能非常小，但在网站后端或处理大量内容时，算法的效率会明显影响系统的延迟和响应速度。对于硬件性能和内存有限的嵌入式设备，需要尽可能优化的方法来处理内容。

常见的算法

算法在这个领域从学习的角度来看实际上就是解题和编程，从如何用代码实现需求，到如何以更优方式运行，下面将对不同方式进行对比。

爬楼梯问题

有一个楼梯有 n 阶，每次可以走1或2步，有多少种走法

解法一

说明

• 从第0阶开始，每次尝试走1步或2步
• 对每个可能的选择再重复同样的操作，直到到达第n阶

C++

class Solution {
public:
    int climbStairs(int n) {
        return climb(0, n);  // 从第0阶开始
    }

    int climb(int current, int n) {
        if (current == n) return 1;    // 到达顶层
        if (current > n) return 0;     // 超过顶层
        // 从current爬1步或2步
        return climb(current + 1, n) + climb(current + 2, n);
    }
}

此代码为LeetCode 70. Climbing Stairs解题示例，输出在climbStairs函数的return
时间复杂度：O(2ⁿ)，在LeetCode提交会超时

解法二

說明

• 站在第1阶以下的方式只有一种
• 我们保存站在每一阶能有多少种方法上来，climb[0] = 1, climb[1] = 1
• 抵达第2阶可以是从第1阶爬上来的，或从第0阶一次爬2阶上来
• 抵达第n阶可以是从第n-1阶爬上来的，或从第n-2阶爬上来
• 只能从n-1或n-2阶上来，互斥事件的方法总和用加法，所以 climb[n] = climb[n-1] + climb[n-2]

C++

#include <vector>

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp = {1, 1};
        for(int i = 2; i <= n ; i++){
            dp.push_back(dp[i-1] + dp[i-2]);
        }
        return dp[n];
    }
};

此代码为LeetCode 70. Climbing Stairs解题示例，输出在climbStairs函数的return
时间复杂度：O(n)，在LeetCode提交可以通过

解法三

說明

从输出结果可以发现这就是一个斐波那契数列，我们应该直接贴一个Fibonacci数组，根据题目的n上限45，所以查找fib[45]需要46个元素

C++

class Solution {
public:
    int climbStairs(int n) {
        int fib[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903};
        return fib[n];
    }
};

此代码为LeetCode 70. Climbing Stairs解题示例，输出在climbStairs函数的return
时间复杂度：O(1)，在LeetCode提交可以通过，是最佳解

结论

提升解题能力和算法水平，是学习编程的良好过程。掌握算法的同时，也能轻松编写复杂的程序逻辑。