Problem: 118. 杨辉三角
思路
👨🏫 参考地址
复杂度
时间复杂度:
添加时间复杂度, 示例: O ( n ) O(n) O(n)
空间复杂度:文章来源:https://www.toymoban.com/news/detail-798651.html
添加空间复杂度, 示例: O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-798651.html
💖 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);//第一行固定是 1
if (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);// 左边固定一个 1
for (int j = 1; j < i; j++)
cur.add(pre.get(j) + pre.get(j - 1));
cur.add(1);// 右边固定一个 1
ans.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;
}
}
到了这里,关于力扣hot100 杨辉三角 递归 DP的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!