力扣hot100 杨辉三角 递归 DP

发布时间:2024年01月16日

Problem: 118. 杨辉三角

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

思路

👨?🏫 参考地址

复杂度

时间复杂度:

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

空间复杂度:

添加空间复杂度, 示例: O ( n ) 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);//第一行固定是 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;
    }
}
文章来源:https://blog.csdn.net/lt6666678/article/details/135623817
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。