08_杨辉三角

简介: 08_杨辉三角

118. 杨辉三角

给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中,每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

  • 1 <= numRows <= 30

【思路】

1、dp数组的含义

dp:定义状态dp[i][j]为杨辉三角中第i行第j列(行索引从0开始)的元素值。

2、递推公式

dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

3、初始化dp数组

每一行第一个元素和最后一个元素都是1,即当i = 0或j=i时,dp[i][j]=1。

4、确定遍历顺序

5、打印dp数组

public class Solution {
  public List<List<Integer>> generate(int numRows) {
    //初始化动态规划数组
    Integer[][] dp = new Integer[numRows][];
    //遍历每一行
    for (int i = 0; i < numRows; i++) {
      //初始化当前行
      dp[i] = new Integer[i + 1];
      //每一行的第一个和最后一个元素为1;
      dp[i][0] = dp[i][i] = 1;
      //计算中间元素
      for (int j = 1; j < i; j ++) {
        //中间元素等于上一行的相邻两个元素之和
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      }
    } 
    //将动态规划数组转换为结构列表
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    for (Integer[] row: dp) {
      result.add(Arrays.asList(row));
    }
    //返回结果列表
    return result;
  }
}
相关文章
|
Linux 测试技术 数据库
达梦(DM)数据库安装
简述windows环境下达梦(DM)数据库安装操作
|
12月前
|
运维 安全 Linux
Linux中传输文件文件夹的10个scp命令
【10月更文挑战第18天】本文详细介绍了10种利用scp命令在Linux系统中进行文件传输的方法,涵盖基础文件传输、使用密钥认证、复制整个目录、从远程主机复制文件、同时传输多个文件和目录、保持文件权限、跨多台远程主机传输、指定端口及显示传输进度等场景,旨在帮助用户在不同情况下高效安全地完成文件传输任务。
1215 5
|
算法 JavaScript
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
224 0
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
|
12月前
|
数据采集 前端开发 算法
Python Requests 的高级使用技巧:应对复杂 HTTP 请求场景
本文介绍了如何使用 Python 的 `requests` 库应对复杂的 HTTP 请求场景,包括 Spider Trap(蜘蛛陷阱)、SESSION 访问限制和请求频率限制。通过代理、CSS 类链接数控制、多账号切换和限流算法等技术手段,提高爬虫的稳定性和效率,增强在反爬虫环境中的生存能力。文中提供了详细的代码示例,帮助读者掌握这些高级用法。
638 1
Python Requests 的高级使用技巧:应对复杂 HTTP 请求场景
|
12月前
|
缓存 网络协议 JavaScript
【HTTP】构造HTTP请求和状态码
【HTTP】构造HTTP请求和状态码
190 1
【HTTP】构造HTTP请求和状态码
|
12月前
|
NoSQL 数据可视化 Linux
redis学习四、可视化操作工具链接 centos redis,付费Redis Desktop Manager和免费Another Redis DeskTop Manager下载、安装
本文介绍了Redis的两个可视化管理工具:付费的Redis Desktop Manager和免费的Another Redis DeskTop Manager,包括它们的下载、安装和使用方法,以及在使用Another Redis DeskTop Manager连接Redis时可能遇到的问题和解决方案。
1359 1
redis学习四、可视化操作工具链接 centos redis,付费Redis Desktop Manager和免费Another Redis DeskTop Manager下载、安装
|
11月前
|
安全 API 数据安全/隐私保护
常见的HTTP请求方法
【10月更文挑战第25天】这些HTTP请求方法共同构成了客户端与服务器之间交互的基础,使得客户端能够根据不同的需求对服务器资源进行各种操作。在实际应用中,开发者需要根据具体的业务场景和资源的性质选择合适的请求方法来实现客户端与服务器之间的有效通信。
|
缓存 NoSQL 应用服务中间件
Redis实战篇
Redis实战篇
|
缓存 NoSQL 关系型数据库
|
12月前
|
小程序 算法 前端开发
微信小程序---授权登录
微信小程序---授权登录
265 0