地址
难度
简单
题目
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
提示:
- 0 <= rowIndex <= 33
进阶：
你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
思路
- 动态规划
与杨辉三角的动态规划一样，只需要一层一层的求。但是不需要把每一层的结果都保存起来，只需要保存上一层的结果，就可以求出当前层的结果了。
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> list =new ArrayList<Integer>();
List<Integer> tmp = new ArrayList<Integer>();
for(int i = 0 ;i<rowIndex+1;i++){
tmp = new ArrayList<Integer>();
for(int j=0;j<i+1;j++){
if(j==0||j==i){
tmp.add(1);
}else {
tmp.add(list.get(j-1)+list.get(j));
}
}
list = tmp;
}
return list;
}
}
- 公式
杨辉三角其实可以看做由组合数构成.其公式为:
最后可以等价于
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> list =new ArrayList<Integer>();
long pre =1;
list.add((int) pre);
for(int i=1;i<rowIndex+1;i++){
long tmp = pre*(rowIndex - i + 1)/i;
list.add((int) tmp);
pre = tmp;
}
return list;
}
}