前言说明
算法学习，日常刷题记录。
题目连接
题目内容
给定一个非负索引k，其中k ≤ 33，返回杨辉三角的第k行。
杨辉三角.gif
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 3
输出: [1,3,3,1]
进阶：
你可以优化你的算法到O(k)空间复杂度吗？
分析过程
前面已经写了另一道杨辉三角的解答方法，请看文章：杨辉三角
前面一道的杨辉三角是返回杨辉三角的前numRows行，而这一道是返回杨辉三角的第k行。
注意：这里的k是索引k，输入3，输出的是[1,3,3,1]，从图中可以看出这是第4行，所以这里的k是从0开始的，而不是从1开始。
那我们先直接复用前面那道题的代码，取第k行的元素，代码如下：
class Solution {
public List<Integer> getRow(int rowIndex) {
// 定义杨辉三角列表
List<List<Integer>> dataList = new ArrayList<>();
// 构造杨辉三角，每次构造一行，这里的rowIndex要加1，因为从0开始算的
for (int i = 0; i < rowIndex + 1; ++i) {
// 定义杨辉三角单行列表
List<Integer> list = new ArrayList<>();
// 第一列
list.add(1);
if (i > 0) {
// 第一行之后
// 获取上一行的结果
List<Integer> listTemp = dataList.get(i - 1);
// 遍历上一行的结果，从第二列到最后一列
for (int j = 1; j < listTemp.size(); ++j) {
// 若不是第一列和最后一列，第n行第m列等于上一行第m-1列+第m列
list.add(listTemp.get(j - 1) + listTemp.get(j));
}
// 最后一列
list.add(1);
dataList.add(list);
} else {
// 第一行
dataList.add(list);
}
}
// 取第rowIndex行的元素返回
return dataList.get(rowIndex);
}
}
执行用时3ms，时间击败43.74%的用户，内存消耗36.4MB，空间击败15.27%的用户。
运行结果
运行时间和空间不是很理想，因为定义了List<List<Integer>>，但是返回的却是List<Integer>，这里生成的前k行占用了多余的空间。
其实只申请一个List<Integer>就可以解决，使用动态规划，用上一次的结果计算下一次的结果，因为杨辉三角的第k行是由第k - 1行计算得出的，第k行第m列 = 第k-1行第m-1列 + 第k-1行第m列。
解答代码
通过上述分析，采用动态规划的代码如下：
class Solution {
public List<Integer> getRow(int rowIndex) {
// 动态规划，用上一次的结果计算下一次的结果
List<Integer> list = new ArrayList<>();
// 第一列
list.add(1);
if (rowIndex == 0) {
return list;
}
// 获取上一次的结果
List<Integer> listTemp = getRow(rowIndex - 1);
// 遍历上一次的结果，从第二列到最后一列
for (int i = 1; i < listTemp.size(); ++i) {
// 若不是第一列和最后一列，第n行第m列等于上一行第m-1列+第m列
list.add(listTemp.get(i - 1) + listTemp.get(i));
}
// 最后一列
list.add(1);
return list;
}
}
提交结果
执行用时1ms，时间击败84.08%的用户，内存消耗36.1MB，空间击败72.11%的用户。
运行结果
原文链接
原文链接：杨辉三角II
