1. 题目

2. 读题（需要重点注意的东西）

思路（滚动数组）：

即将[LeetCode]118. 杨辉三角（java实现）递推的空间优化到O(n)，一般dp问题将二维优化到一维，可以考虑滚动数组。

滚动数组的特点： f[i][j] = f[i-1][j-1] + f[i-1][j]; 当算这一层的值的时候，只用到了上一层的值，因此可以通过滚动数组将二维优化成一维。

用滚动数组将二维优化成一维的步骤：（这种转换方式是固定的，背下来）
1. 先用二维的方法写完（见解法:优化前）
2. 将声明中的行数改为2
int[][] f = new int[2][rowIndex+1];
3. 将所有二维行 i 的后面加上& 1即可

```java
if(j == 0) f[i & 1][j] = 1;
if(i == j) f[i & 1][j] = 1;
if(i > 0 && j > 0) f[i & 1][j] = f[i-1 & 1][j-1] + f[i-1 & 1][j];
if(i == rowIndex) res.add(f[i & 1][j]);
```

3. 解法

---------------------------------------------------解法:优化前---------------------------------------------------

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        int[][] f = new int[rowIndex+1][rowIndex+1];

        for(int i = 0;i <= rowIndex;i++){
            for(int j = 0;j <= i;j++){

                if(j == 0) f[i][j] = 1;
                if(i == j) f[i][j] = 1;
                if(i > 0 && j > 0) f[i][j] = f[i-1][j-1] + f[i-1][j];

                if(i == rowIndex) res.add(f[i][j]);
            }
        }
        return res;
    }
}

可能存在的问题：

---------------------------------------------------解法:滚动数组优化后---------------------------------------------------

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>();
        // 声明里改为2
        int[][] f = new int[2][rowIndex+1];

        for(int i = 0;i <= rowIndex;i++){
            for(int j = 0;j <= i;j++){
                // 每个i后面加上 &1
                if(j == 0) f[i & 1][j] = 1;
                if(i == j) f[i & 1][j] = 1;
                if(i > 0 && j > 0) f[i & 1][j] = f[i-1 & 1][j-1] + f[i-1 & 1][j];

                if(i == rowIndex) res.add(f[i & 1][j]);
            }
        }
        return res;
    }
}

可能存在的问题：

问题： 为什么是&1？

回答：
每一次只需要当前行和上一行两行的数据，因此我们用两行数组滚动存储这两行的信息，n为行数：
f[0][rowIndex+1] 存储第0 、2、4、6、8… 行（n % 2 == 0）
f[1][rowIndex+1] 存储第1、3、5、7、9… 行 （n % 2 == 1）
看起来就好像数组在滚动一般，因此称为滚动数组。

因此用n % 2就可以知道这一行用 f[0][rowIndex+1] 存储还是用 f[1][rowIndex+1] 存储；又n % 2等价于 n & 1，因此在每一个 i 后 &1 就能得到当前层的数据和上一层的数据。

4. 可能有帮助的前置习题

• [LeetCode]118. 杨辉三角（java实现）递推

5. 所用到的数据结构与算法思想

• 滚动数组

6. 总结

滚动数组的优化方式是固定的，背下来即可。