爬楼梯问题是动态规划经典题：每次走1或2阶，求到第n阶的走法数；状态转移方程为dp[i]=dp[i−1]+dp[i−2]，边界dp[0]=dp[1]=1，PHP可用双变量滚动优化实现。
爬楼梯问题是什么
爬楼梯是动态规划入门经典题：每次可以走1阶或2阶，问走到第n阶有多少种不同走法。比如n=3时，有3种走法（1+1+1、1+2、2+1）。
状态定义与转移方程
设$dp[$i]表示走到第$i阶的方法数。因为最后一步只能从第$i-1阶（迈1步）或第$i-2阶（迈2步）过来，所以：
$dp[$i] = $dp[$i-1] + $dp[$i-2]
边界条件：$dp[0] = 1（站在地面算1种方案），$dp[1] = 1（到第1阶只有1种走法）。
立即学习“PHP免费学习笔记（深入）”；
PHP动态规划实现（空间优化版）
不需要保存整个数组，只用两个变量滚动更新，节省空间：
function climbStairs($n) {
if ($n <= 1) return 1;
$prev2 = 1; // dp[0]
$prev1 = 1; // dp[1]
for ($i = 2; $i <= $n; $i++) {
$current = $prev1 + $prev2;
$prev2 = $prev1;
$prev1 = $current;
}
return $prev1;
}
// 示例调用
echo climbStairs(5); // 输出 8
常见变体与注意事项
- 若允许走1/2/3阶，状态转移变为：$dp[$i] = $dp[$i-1] + $dp[$i-2] + $dp[$i-3]，需补全前三个初始值
- n为0时返回1是合理设定（不爬也是一种方案），部分题目可能要求n≥1，注意审题
- 递归写法容易超时（指数级），务必用迭代或记忆化递归
- 结果可能溢出，PHP中整数一般够用，但n极大时可考虑取模（如%1000000007）
