方法1:动态规划
时间复杂度:$O(rowIndex^2)$
空间复杂度:$O(1)$
解题思路
https://leetcode.cn/problems/pascals-triangle-ii/solution/119yang-hui-san-jiao-ii-dong-tai-gui-hua-by-ceng-j/
总的来说就是利用杨辉三角形后一行与前一行的关系。
更新过程为:从倒数第二个元素开始往前更新 它等于原来这个位置的数 + 前一个位置的数。
Java 代码
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i <= rowIndex; i ++) {
list.add(1);//每一行都是末尾加个1,(rowIndex + 1)次原地修改list
for (int j = list.size() - 2; j > 0; j --) {//从倒数第二个开始往前修改
list.set(j, list.get(j) + list.get(j - 1));
}
}
return list;
}
}