爬楼梯这个问题也是一个很经典的面试题，可以换各种人物动物，比如青蛙、小兔子跳台阶，张三李四爬楼梯等等。
题目会类似于下面这样：
假设你正在爬楼梯，需要 n 阶你才能到达楼顶，每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
假设有 2 个台阶，那么有两种方法可以爬到楼顶：
- 1 个台阶 + 1 个台阶
- 2 个台阶
- 1 个台阶 + 1 个台阶 + 1 个台阶
- 1 个台阶 + 2 个台阶
- 2 个台阶 + 1 个台阶
- 1 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶
- 1 个台阶 + 1 个台阶 + 1 个台阶 + 2 个台阶
- 1 个台阶 + 2 个台阶 + 2 个台阶
- 2 个台阶 + 2 个台阶 + 1 个台阶
- 2 个台阶 + 1 个台阶 + 2 个台阶
- 2 个台阶 + 1 个台阶 + 1 个台阶 + 1 个台阶
- 1 个台阶 + 2 个台阶 + 1 个台阶 + 1 个台阶
- 1 个台阶 + 1 个台阶 + 2 个台阶 + 1 个台阶
假设爬到楼顶的方法为
f(n)，根据题目意思有两种可能- 爬一个台阶：
f(n-1) - 爬两个台阶：
f(n?2)
f(n) = f(n-1) + f(n-2)这样我们就可以使用递归来实现：
但在递归时也需要处理边界问题，比如
f(1) = 1，f(2) = 2，这两种情况我们可以直接返回，而不需要递归。所以可以得到这样的递归函数：
function climbStairs($n) {
if ($n == 1) return 1;
if ($n == 2) return 2;
return climbStairs($n - 1) + climbStairs($n - 2);
}echo climbStairs(2);
// 2
echo climbStairs(3);
// 3
echo climbStairs(5);
// 8再来看看使用循环是否能解决问题？
假设我们使用循环来实现，那么可以使用一个数组来保存已经计算过的值，假设使用一个数组
dp[]来保存爬一个台阶有多少种方法：【不管是青蛙跳台阶还是who爬楼梯，能上去就行】
dp[n] = dp[n-1] + dp[n-2]和递归一样，也满足
dp[1] = 1, dp[2] = 2，可以得到以下函数function climbStairs($n) {
$dp = [];
$dp[1] = 1;
$dp[2] = 2;
for ($i = 3;
$i <= $n;
$i++) {
$dp[$i] = $dp[$i - 1] + $dp[$i - 2];
}
return $dp[$n];
}在使用递归时，我们是从最后一个台阶开始，朝着底下的台阶去找，并不确实下一个是不是终点，只能一个一个去找。
而在使用循环时，我们是从第一个台阶开始，往上爬，这个时候是知道前面的方法个数的，直接拿来用就好了，不用再重新算了。
echo climbStairs(3), PHP_EOL;
// 3
echo climbStairs(4), PHP_EOL;
// 5
echo climbStairs(5), PHP_EOL;
// 8
echo climbStairs(6), PHP_EOL;
// 13
echo climbStairs(7), PHP_EOL;
// 21
echo climbStairs(8), PHP_EOL;
// 34上面的枚举也可以验证我们的猜想，实际上我们只需要知道：
当前方法个数 = 前一个方法个数 + 前前一个方法个数。假设
f为当前方法个数，a和b分别为前一个和前前一个的方法个数，可以得到一个新的循环方式：我们是从第
0 级开始爬的，从第 0 个到第 0 个台阶，我们也可以当成一种方法，即f=1function climbStairs($n) {
$a = $b = 0;
$f = 1;
for ($i = 1;
$i <= $n;
$i++) {
$a = $b;
$b = $f;
$f = $a + $b;
}
return $f;
}以上就是一个动态规划的代码，直接看的话可能比较难懂为什么这么写，经过递归和循环的验证与理解，看上去就很简单了。
在面试中遇到算法题时不要慌，可以先从简单暴力的方法入手，再尝试有没有最优解。
同时也建议有空时可以去力扣刷刷算法题，理解一些相关概念和思路，这样就不会在遇到算法题时恐慌，不知道该从何处入手了。
除此之外也要熟悉所用的语言，特别是内置的一些函数方法，比如验证一个数是不是回文数时，PHP 就可以使用 strrev 函数，将它进行反转后再进行比较就可以直接判断是与否了。
$n1 = 21;
$n2 = 22;
$n3 = -22;
var_dump(strrev($n1) == $n1);
var_dump(strrev($n2) == $n2);
var_dump(strrev($n3) == $n3);
面试后记得及时复盘，下次肯定比这次更好~
本文参与了 SegmentFault 思否征文「如何“反杀”面试官？」，欢迎正在阅读的你也加入。
