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
yum镜像源汇总
yum镜像源汇总
5461 0
|
2月前
|
人工智能 运维 BI
QwenWork 千问办公实战全指南:Qwen3.8 基座六大核心能力,桌面与云端 Agent、API 示例及计费选型解析
本文完整梳理QwenWork产品定位、Qwen3.8基座带来的技术增益、六大核心能力、各行业落地业务场景,提供curl、Python底层API可运行代码,拆解席位+积分混合计费体系,讲解参数调优、业务选型、高频故障排查,帮助个人从业者、企业技术管理者理清产品能力边界,完成POC验证和业务落地。
501 3
|
2月前
|
人工智能 自然语言处理 文字识别
阿里云有哪些AI产品可免费试用?超30款AI产品和1亿+大模型 tokens免费体验
阿里云AI产品免费试用活动面向认证新用户开放,覆盖超30款AI产品与至高1亿+大模型Tokens。权益包含阿里云百炼1亿+Tokens限免体验、PAI全链路AI开发免费算力、多款NLP与视觉智能产品百万级调用额度,还支持预约AI专家获取专属POC服务,零成本帮助开发者与企业完成AI应用前期探索与验证。
|
2月前
|
人工智能 架构师 Java
测试专用大模型 CodeLlama-34B-Test 深度解析:AI驱动的软件测试新范式
CodeLlama-34B-Test是基于Llama 2微调的开源测试专用大模型,参数达340亿,HumanEval准确率53.7%(微调后超73%)。首创融合轻量级符号执行,实现语义理解+路径推导,显著提升单元测试生成质量与业务覆盖能力,正重塑AI时代软件质量保障范式。
|
3月前
|
人工智能 缓存 API
‌DeepSeek V4 Pro在阿里云怎么调用?阿里云百炼支持‌DeepSeek V4 Pro吗?
阿里云百炼正式支持DeepSeek V4 Pro(模型ID:deepseek-v4-pro),支持OpenAI/DashScope/Anthropic兼容调用,享免费100万Tokens。支持思考模式、Function Calling及百万级上下文,可按量付费或订阅TokenPlan(个人版39元/月)。在阿里云百炼官网:https://t.aliyun.com/U/fPVHqY 免费领取千万Tokens
|
3月前
|
存储 弹性计算 运维
租赁系统哪类好:基于阿里云生态的架构设计与选型考量
本文剖析租赁系统SaaS、入驻平台与私有化三种部署模式的本质差异,聚焦阿里云生态下私有化五层架构(接入、业务、风控、数据、运维),提供涵盖数据归属、资金链路、风控自主性等6维度的选型评估清单,助力企业基于经营周期与合规需求做出理性决策。
|
弹性计算 监控 并行计算
如何在阿里云上部署满血版DeepSeek
在阿里云部署“满血版”DeepSeek模型,需合理配置硬件与软件环境。首先注册阿里云账号并申请GPU计算型ECS实例(推荐V100/A10/A100),配置安全组规则。接着安装NVIDIA驱动、CUDA及Python依赖库,下载DeepSeek模型权重并克隆代码仓库。通过FastAPI编写推理接口,使用Uvicorn运行服务,支持反向代理与HTTPS配置。最后优化显存、监控性能,确保高效稳定运行。
如何在阿里云上部署满血版DeepSeek
|
SQL 关系型数据库 MySQL
MySQL入门指南:从安装到第一个查询
本文为MySQL数据库入门指南,内容涵盖从安装配置到基础操作与SQL语法的详细教程。文章首先介绍在Windows、macOS和Linux系统中安装MySQL的步骤,并指导进行初始配置和安全设置。随后讲解数据库和表的创建与管理,包括表结构设计、字段定义和约束设置。接着系统介绍SQL语句的基本操作,如插入、查询、更新和删除数据。此外,文章还涉及高级查询技巧,包括多表连接、聚合函数和子查询的应用。通过实战案例,帮助读者掌握复杂查询与数据修改。最后附有常见问题解答和实用技巧,如数据导入导出和常用函数使用。适合初学者快速入门MySQL数据库,助力数据库技能提升。
|
存储 算法 Go
【LeetCode 热题100】17:电话号码的字母组合(详细解析)(Go语言版)
LeetCode 17题解题思路采用回溯算法,通过递归构建所有可能的组合。关键点包括:每位数字对应多个字母,依次尝试;递归构建下一个字符;递归出口为组合长度等于输入数字长度。Go语言实现中,使用map存储数字到字母的映射,通过回溯函数递归生成组合。时间复杂度为O(3^n * 4^m),空间复杂度为O(n)。类似题目包括括号生成、组合、全排列等。掌握回溯法的核心思想,能够解决多种排列组合问题。
804 11
|
Windows Perl
AVL树(平衡二叉搜索树)
nt _bf;, _bf(0), _kv(kv){}某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子(BF,Balance Factor),平衡二叉树中不存在平衡因子大于 1或小于-1的节点。在一棵平衡二叉树中,节点的平衡因子只能取 0 、1 或者 -1 ,分别对应着左右子树等高,左子树比较高,右子树比较高。
592 0