共计 1896 个字符，预计需要花费 5 分钟才能阅读完成。
爬楼梯这个问题也是一个很经典的面试题，能够换各种人物动物，比方青蛙、小兔子跳台阶，张三李四爬楼梯等等。
题目会相似于上面这样：
假如你正在爬楼梯，须要 n 阶你能力达到楼顶，每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？
假如有 2 个台阶，那么有两种办法能够爬到楼顶：
- 1 个台阶 + 1 个台阶
- 2 个台阶
假如有 3 个台阶，那么有三种办法能够爬到楼顶：
- 1 个台阶 + 1 个台阶 + 1 个台阶
- 1 个台阶 + 2 个台阶
- 2 个台阶 + 1 个台阶
假如有 5 个台阶，那么有八种办法能够爬到楼顶：
- 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[] 来保留爬一个台阶有多少种办法：
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=1
function 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 思否征文「如何“反杀”面试官？」，欢送正在浏览的你也退出。