Problem: 118. 杨辉三角

思路

👨‍🏫 参考地址

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

💖 DP

class Solution {public List<List<Integer>> generate(int numRows){List<List<Integer>> ans = new ArrayList<>();ans.add(new ArrayList<>());ans.get(0).add(1);//第一行固定是 1if (numRows == 0)return ans;List<Integer> pre = ans.get(0);// pre记录当前行的前一行for (int i = 1; i < numRows; i++){List<Integer> cur = new ArrayList<>();cur.add(1);// 左边固定一个 1for (int j = 1; j < i; j++)cur.add(pre.get(j) + pre.get(j - 1));cur.add(1);// 右边固定一个 1ans.add(cur);pre = cur;}return ans;}
}

💖 从下往上递归

class Solution {public List<List<Integer>> generate(int numRows) {//存储要返回的杨辉三角List<List<Integer>> dg = new ArrayList<>();//若0行，则返回空if(numRows == 0){return dg;}//递归出口，这是第一步！找到出口if(numRows == 1){dg.add(new ArrayList<>());dg.get(0).add(1);return dg;}//递归，注意返回值！！！这是第二步dg = generate(numRows-1);//一级递归要做啥，我们可以看第二行到第三行需要做啥//首先是要申请一个list来存储第三行，然后通过第二行得到第三行//第三行的首尾为1是确定了的，然后就是中间的数如何得到//通过观察很容易拿到for循环里面的式子//最后别忘了返回值！！！List<Integer> row = new ArrayList<>();row.add(1);for(int j = 1;j < numRows - 1;j++){row.add(dg.get(numRows-2).get(j-1) + dg.get(numRows-2).get(j));}row.add(1);dg.add(row);return dg;}
}