本文共 1213 字，大约阅读时间需要 4 分钟。

杨辉三角（Pascal's Triangle）是数学中一种重要的递归结构，每一行的元素可以通过组合数计算得到。本文将介绍如何通过滚动递推的方法计算杨辉三角的指定行。

滚动递推法

为了高效地计算杨辉三角的某一行，我们采用滚动递推的方法。这种方法通过维护两个列表（row1和row2）来实现，每次迭代时只需要将row1和row2交换，并更新row1的元素即可。

方法逻辑

代码实现

import java.util.ArrayList;import java.util.List;public class Solution {    public List
   
     getRow(int rowIndex) {        List
    
      row1 = new ArrayList<>();        List
     
       row2 = new ArrayList<>();        row1.add(1);        row2.add(1);        row2.add(1);        if (rowIndex == 0) {            return row1;        }        if (rowIndex == 1) {            return row2;        }        for (int i = 0; i < rowIndex - 1; i++) {            row1.add(0);        }        for (int j = 1; j < row2.size(); j++) {            row1.set(j, row2.get(j - 1) + row2.get(j));        }        row1.add(1);        List
      
        swap = row1;        row1 = row2;        row2 = swap;        return row2;    }}
      
     
    
   

时空复杂度

该方法的时间复杂度为O(n)，其中n为所需行的索引值。通过滚动递推，我们只需要线性时间来计算每一行的元素。空间复杂度同样为O(n)，主要用于存储当前行和下一行的元素。

这种方法不仅高效，还简化了内存使用，使其适用于大规模计算。

转载地址：http://cqds.baihongyu.com/