力扣 三角dp
动态规划基础题,当前所在元素来自上一行的两列的值。
题目

从图可以看出,每一行的第一个数与最后一个数都是1,然后中间的数是来自它左上方和右上方的数的和。当然并不是要打印这个三角形的形状,因此可以想到正常的打印方式应该是从每一行的左边往右边打的,默认的打印与循环的三角形的每一行每一列应该是这样的。
1
1 2 1
1 3 3 1
1 4 6 4 1
从这里就可以开始写循环遍历了,用外循环i去控制行,然后用j表示每一行的每一列即每个元素,可以看到排除首尾是1的情况,就是当前数由上方跟左上方得来,不需要右上方,按这个排列的图找规律。然后排去首尾特殊的数,还发现到,每一行需要dp的数量跟当前行号是一致的,注意这里的行号从0开始,即第一行有一个数为2,第二行有两个数3、3等等。然后就可以依照这些规律写dp了,这里用了嵌套动态数组去加每一行每一列,里面的数组对应每一行的数组,然后外层即一个大的list了。
状态转移方程为:dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j],这里的get是用来读取arraylist的值。
时间复杂度:O(numRows^2),空间复杂度:O(1)。
class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> res = new ArrayList<List<Integer>>();for (int i = 0; i < numRows; i++) {List<Integer> row = new ArrayList<Integer>();for (int j = 0; j <= i; j++) { //每一行的数量是行号if (j == 0 || j == i) {row.add(1);//每一行的首尾} else {row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));//由上一个跟上一个的附近一个得来}}res.add(row);//加入每一行}return res;}
}
动态规划找规律写状态转移方程还是很重要的。
相关文章:
力扣 三角dp
动态规划基础题,当前所在元素来自上一行的两列的值。 题目 从图可以看出,每一行的第一个数与最后一个数都是1,然后中间的数是来自它左上方和右上方的数的和。当然并不是要打印这个三角形的形状,因此可以想到正常的打印方式应该是…...
SQL基础语法全解析(上篇)
一、基本概念 1. 数据库术语 数据库(database) - 保存有组织的数据的容器(通常是一个文件或一组文件)。数据表(table) - 某种特定类型数据的结构化清单。模式(schema) - 关于数据库…...
【笔记】Linux服务器端使用百度网盘
1、在python环境下,下载bypy pip install bypy 2、第一次连接需要认证 bypy info 认证通过后百度网盘会出现bypy文件夹,如下 3、查看当前文件夹下的文件 bypy list 若有很多文件夹,可在后面增加文件夹名称,列出对应位置下的文件&a…...
UEFI Spec 学习笔记---3 - Boot Manager(3)
3.2 Boot Manager Policy Protocol EFI_BOOT_MANAGER_POLICY_PROTOCOL----EFI应用程序使用该协议请求UEFI引导管理器使用平台策略连接设备。 typedef struct _EFI_BOOT_MANAGER_POLICY_PROTOCOL EFI_BOOT_MANAGER_POLICY_PROTOCOL; struct _EFI_BOOT_MANAGER_POLICY_PROTOCOL…...
ATTCK红队评估实战靶场(四)
靶机链接:http://vulnstack.qiyuanxuetang.net/vuln/detail/6/ 环境搭建 新建两张仅主机网卡,一张192.168.183.0网段(内网网卡),一张192.168.157.0网段(模拟外网网段),然后按照拓补…...
Android Studio 历史版本下载
Android Studio 历史版本下载 官方链接:https://developer.android.google.cn/studio/archive 通过gradle插件版本反查Android Studio历史版本 Android Studio Ladybug | 2024.2.1 October 1, 2024 【https://redirector.gvt1.com/edgedl/android/studio/ide-zip…...
微信小程序px和rpx单位互转方法
js代码如下 Page({data: {width: 0,width2: 0},onLoad: function (options) {let px this.pxToRpx(380)let rpx this.rpxToPx(730.7692307692307) // 检查两个互转是否是相同即可,例如pxToRpx(380)转成730.7692307692307 则rpxToPx(730.7692307692307)如果是380则代表互转没…...
Vercel 部署与管理指南:简化前端应用的自动化部署流程
引言 在现代的前端开发中,部署和托管项目一直是开发者关注的重要环节。Vercel,作为一个专注于简化前端开发和部署的平台,凭借其强大的自动化功能、全球内容分发网络(CDN)以及对 Next.js 等框架的优越支持,…...
Java11使用JVM同一日志框架启用日志记录
你可以使用-Xlog选项配置或启用Java虚拟机同一日志框架的日志记录。 -Xlog:gc*trace:file/Users/xx/gc-%t.log:time,tags,level,pid,tid,hostname,path:filecount3,filesize10K -Xlog:gc*trace:stdout:time,tags,level,pid,tid,hostname:filecount3,filesize10K -Xlog:gc*trac…...
onlyoffice实现文档比对(Beta版)-纯文字比对(非OCR)
一、说明 文档比对光靠前端或者后端是无法实现的。 该文中的实现方案为:onlyofficejava。java进行文档差异化比较并输出对比结果,only进行得到结果处理渲染。 此方案目前为Beta版本,简单Word Demo实现了比对结果。css、关联动态效果登将在后期…...
JS querySelector方法的优点
1. 灵活性 支持所有 CSS 选择器 ID 选择器:#id 示例:document.querySelector(#myId)解释:选择 id 为 myId 的元素。类选择器:.class 示例:document.querySelector(.myClass)解释:选择具有 class 为 myCla…...
利用获取商品详情API:item_get可以获取到淘宝商品详情的哪些数据?
先来看下测试的返回数据吧 items: { total_results: 76, totalpage: 8, page_size: 10, page: "1", item: [ { rate_content: "和我家的鞋柜特别搭,加上这一条遮挡布,感觉整洁多了,布料不是硬邦邦的那种,很满意。…...
【大数据学习 | 面经】Spark 3.x 中的AQE(自适应查询执行)
Spark 3.x 中的自适应查询执行(Adaptive Query Execution,简称 AQE)通过多种方式提升性能,主要包括以下几个方面: 动态合并 Shuffle 分区(Coalescing Post Shuffle Partitions): 当 …...
[Vue]Vue-router
路由 对前端路由的理解 在前端技术早期,一个 url 对应一个页面,如果要从 A 页面切换到 B 页面,那么必然伴随着页面的刷新。这个体验并不好,不过在最初也是无奈之举——用户只有在刷新页面的情况下,才可以重新去请求数…...
【HarmonyOS】鸿蒙应用使用lottie动画
【HarmonyOS】鸿蒙应用使用lottie动画 一、lottie动画是什么? https://airbnb.design/lottie Lottie是由Airbnb团队开发的一个适用于iOS、Android、React Native、Web和Windows的开源动画库,用于解析使用Bodymovin导出为JSON的Adobe After Effects动…...
1.使用docker 部署redis Cluster模式 集群3主3从
1.使用docker 部署redis Cluster模式 集群3主3从 1.1 先安装docker 启动docker服务,拉取redis镜像 3主3从我们要在docker启动6个容器docker run --name redis-node-1 --net host --privilegedtrue -v /data/redis/share/redis-node-1:/data redis:6.0.8 --cluster-…...
vue基础之8:computed对比watch
欢迎来到“雪碧聊技术”CSDN博客! 在这里,您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者,还是具有一定经验的开发者,相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导,我将…...
Luban数据插件的用法
配置后数据后,点击图1中的gen.bat文件启动生成配置数据和解析配置数据代码的程序,自动生成配置数据和解析用到的代码;因为我已经 指定了生成内容的输出路径为Unity项目的路径下面,所以,不用再搬运生成的内容到项目目录…...
指针(上)
目录 内存和地址 指针变量和地址 取地址(&) 解引用(*) 大小 类型 意义 const修饰 修饰变量 修饰指针 指针运算 指针- 整数 指针-指针 指针的关系运算 野指针 概念 成因 避免 assert断言 指针的使用 strl…...
张伟楠动手学强化学习笔记|第一讲(上)
张伟楠动手学强化学习笔记|第一讲(上) 人工智能的两种任务类型 预测型任务 有监督学习无监督学习 决策型任务 强化学习 序贯决策(Sequential Decision Making) 智能体序贯地做出一个个决策,并接续看到新的观测,知道最终任务结…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
2.3 物理层设备
在这个视频中,我们要学习工作在物理层的两种网络设备,分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间,需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质,假设A节点要给…...
