---
### 🔍 **空间优化法详解**
#### **1. 什么是空间优化法？**
空间优化法是在动态规划的基础上，**通过减少存储状态的数量来压缩内存占用**的优化策略。其核心思想是：**只保留解决问题所必需的最小状态集合**，而非存储所有中间结果。
---
#### **2. 为什么需要空间优化？**
- **内存限制**：当问题规模极大时（如 `n=10^5`），动态规划的数组存储会占用大量内存，甚至导致内存溢出。
- **效率提升**：减少内存访问次数，提升缓存命中率，优化程序运行效率。
- **环保思维**：在保证时间效率的前提下，追求极致的空间节省，符合算法优化的“绿色计算”理念。
---
#### **3. 空间优化法的实现原理（以爬楼梯问题为例）**
**关键观察**：
在爬楼梯问题中，递推公式为 `f(n) = f(n-1) + f(n-2)`。
实际上，**当前状态仅依赖前两个状态**，无需存储全部历史值。
**滚动变量法操作步骤**：
1. **初始化变量**：
- `a = f(1) = 1`（到达第1阶的方法数）
- `b = f(2) = 2`（到达第2阶的方法数）
2. **滚动更新**：
从第3阶开始迭代，每次用 `c = a + b` 计算当前阶方法数，然后更新 `a` 和 `b`：
- `a` 更新为前一阶的 `b`（即 `f(n-1)`）
- `b` 更新为当前阶的 `c`（即 `f(n)`）
3. **终止条件**：
遍历到第 `n` 阶时，`b` 即为最终结果。
---
#### **4. 代码实现与注释**
```java
public static int climbingStairs(int n) {
if (n <= 2) return n; // 直接返回边界值
int a = 1, b = 2, c; // 仅需3个变量
for (int i = 3; i <= n; i++) {
c = a + b; // 计算当前阶方法数
a = b; // 更新前两个状态
b = c;
}
return b; // 最终结果存储在b中
}
```
**代码解析**：
- **变量含义**：
- `a`：模拟 `f(n-2)`
- `b`：模拟 `f(n-1)`
- `c`：计算 `f(n)`
- **更新逻辑**：
每次循环后，`a` 和 `b` 向前滚动一步，始终保存最新的两个状态。
---
#### **5. 动态规划 VS 空间优化法**
| **对比维度** | **动态规划** | **空间优化法** |
|--------------------|-----------------------------|-----------------------------|
| 空间复杂度 | O(n)（存储所有状态） | O(1)（仅需3个变量） |
| 内存占用 | 高（随n线性增长） | 极低（恒定3个变量） |
| 适用场景 | 通用问题，代码可读性强 | 大规模数据或内存敏感场景 |
| 代码复杂性 | 简单直观 | 需要理解状态滚动逻辑 |
---
#### **6. 实战应用场景**
- **高频面试题**：爬楼梯、斐波那契数列、路径规划等问题。
- **工程优化**：嵌入式开发、物联网设备等内存受限环境。
- **算法竞赛**：处理输入规模极大的题目（如 `n=1e18` 时需结合矩阵快速幂）。
---
### 🌟 **总结**
空间优化法通过**状态滚动**的巧妙设计，在保持时间复杂度为 `O(n)` 的前提下，将空间复杂度压缩到 `O(1)`。它不仅是算法优化的经典技巧，更是“少即是多”（Less is More）这一哲学思想的代码体现。