力扣hot100 杨辉三角 递归 DP

这篇具有很好参考价值的文章主要介绍了力扣hot100 杨辉三角 递归 DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem: 118. 杨辉三角

力扣hot100 杨辉三角 递归 DP,力扣 hot100,leetcode,算法
力扣hot100 杨辉三角 递归 DP,力扣 hot100,leetcode,算法
力扣hot100 杨辉三角 递归 DP,力扣 hot100,leetcode,算法

思路

👨‍🏫 参考地址

复杂度

时间复杂度:

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

空间复杂度:

添加空间复杂度, 示例: 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】探索杨辉三角模型

    力扣原题 首先我们要来了解一下题目本身在说些什么,通过下方的动图我们可以更加清楚地看到杨辉三角是怎样一步步生成的。 给到的示例中我们通过输入杨辉三角的行数,然后通过计算得到这个杨辉三角的每一行是什么具体的数值 首先我们要做的第一件事就是去选择正确

    2024年02月14日
    浏览(36)
  • leetcode | 杨辉三角 | 电话号码配对

       电话号码的字母组合 杨辉三角                                                                                                                                                                                                                   

    2024年02月22日
    浏览(41)
  • leetcode--杨辉三角(C、C++)

    2024年02月15日
    浏览(41)
  • ***杨辉三角_yyds_LeetCode_python***

    给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2: 输入: numRows = 1 输出: [[1]] 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/pasc

    2024年02月08日
    浏览(43)
  • 杨辉三角(Java)

     实现思路:我们可以先把杨辉三角想象成一个空的二维数组,然后再给它赋值输出即可。 关键在于如何赋值:仔细观察上图可以得出除了 每一行第一个数以及最后一个数(都是1) , 中间的数字规律就是: a[ i ][ j ] = a[ i - 1 ][ j - 1 ] + a[ i - 1 ][ j ] 实现代码: 相信大家更多的

    2024年02月08日
    浏览(37)
  • 【C语言】-- 杨辉三角

    目录 一.什么是杨辉三角? 二.实现方法 1.直角三角形版 2.等腰三角形版 杨辉三角形,又称贾宪三角形,帕斯卡三角形,是二项式系数在三角形中的一种几何排列。 形如: 我们不难看出其存在明显的规律。 即:图片的 两个斜边都是数字1 , 其余的数都等于 它所在层的肩上(

    2024年02月13日
    浏览(46)
  • C练习——杨辉三角

    题目: 打印近似杨辉三角,行数n自选 百度找的杨辉三角,参考一下: 解析: 把它的全部元素左对齐,就可以看成近似杨辉三角的样子 1 1  1 1  2  1 1  3  3  1 1  4  6  4  1 ……  每个数等于它上方两数之和 每行数字左右对称,由1开始逐渐变大 行数与列数相同,第n行有

    2024年01月17日
    浏览(39)
  • 打印杨辉三角

    这个公式,不好算,我觉得还是杨辉三角算起来方便:c#代码如下:    double 打印杨辉三角(int n)//n必须是偶数,展开项是n+1,中间项是n/2,此处返回中间项的概率202306131722         {             //for (int i = 0; i n; i++)             //{             //    //这种方法直接算,使

    2024年02月09日
    浏览(38)
  • 动态规划-杨辉三角

    该算法题分别是: 118. 杨辉三角。 119. 杨辉三角 II 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 1.2.1 示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 1.2.2 示例 2: 输入: numRows = 1 输出: [[1]] 1.2.3 提示: 1 = numRows = 30 来源:力扣(LeetCode) 链接:https://

    2024年02月13日
    浏览(41)
  • 每日一题,杨辉三角

    给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。 示例 1: 示例 2:

    2024年02月04日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包