爬楼梯（带备忘录的斐波那契）1

爬楼梯问题是一个经典的计算机科学问题，它涉及到动态规划和递归算法。在这个问题中，我们假设要达到n阶楼梯的顶部，每次可以走1阶或2阶。目标是找到到达顶部的不同路径数量。 我们可以从最简单的场景开始分析。当只有1阶时，只有一种方法就是直接走上去；如果有2阶，同样有两种方法，即连续走两次1阶或者一次走2阶。这两种情况构成了问题的基础。 题目中提到的"斐波那契数列"与这个问题密切相关。斐波那契数列定义为F(0)=0, F(1)=1, 之后的每一项F(n)都是前两项之和，即F(n) = F(n-1) + F(n-2)。对于爬楼梯问题，到达第n阶楼梯的方法数可以用这个数列来表示。例如，到达3阶楼梯有3种方法，这正是斐波那契数列的第三项：F(3) = F(2) + F(1) = 2 + 1 = 3。 原始的递归解决方案，如注释中的`climbStairs`函数所示，虽然直观，但是效率低下。因为对于较大的n值，会进行大量的重复计算。例如，计算F(n)时需要计算F(n-1)和F(n-2)，而计算F(n-1)时又需要计算F(n-2)和F(n-3)，如此类推，导致大量的重复。 为了解决这个问题，我们可以引入备忘录（也称为记忆化搜索）。备忘录是一个数组，用于存储之前计算的结果，避免重复计算。在这个问题中，我们创建一个大小为100的数组`arr`，并用-1填充，表示未计算的状态。当我们需要计算F(n)时，先检查`arr[n]`，如果已经有值则直接返回，否则通过递归计算`fun(n-1,arr)`和`fun(n-2,arr)`，并将结果存入`arr[n]`。 `fun`函数是备忘录的核心，它接收当前要计算的阶数n和备忘录数组arr作为参数。在函数内部，我们首先检查`arr[n]`，如果已经有值，就直接返回。如果没有，我们通过递归计算当前阶数的方法数，并将其存入备忘录中，然后返回结果。 `climbStairs`函数初始化备忘录数组，并设置基础情况（F(1)=1, F(2)=2），然后调用`fun`函数计算n阶楼梯的方法数。 通过备忘录技术，我们显著减少了递归过程中的重复计算，提高了算法的效率。这个方法是动态规划的一个实例，它通过将问题分解为子问题并存储子问题的解来避免重复工作，从而有效地解决了爬楼梯问题。