当前位置: 首页 > news >正文

力扣 三角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

动态规划基础题&#xff0c;当前所在元素来自上一行的两列的值。 题目 从图可以看出&#xff0c;每一行的第一个数与最后一个数都是1&#xff0c;然后中间的数是来自它左上方和右上方的数的和。当然并不是要打印这个三角形的形状&#xff0c;因此可以想到正常的打印方式应该是…...

SQL基础语法全解析(上篇)

一、基本概念 1. 数据库术语 数据库&#xff08;database&#xff09; - 保存有组织的数据的容器&#xff08;通常是一个文件或一组文件&#xff09;。数据表&#xff08;table&#xff09; - 某种特定类型数据的结构化清单。模式&#xff08;schema&#xff09; - 关于数据库…...

【笔记】Linux服务器端使用百度网盘

1、在python环境下&#xff0c;下载bypy pip install bypy 2、第一次连接需要认证 bypy info 认证通过后百度网盘会出现bypy文件夹&#xff0c;如下 3、查看当前文件夹下的文件 bypy list 若有很多文件夹&#xff0c;可在后面增加文件夹名称&#xff0c;列出对应位置下的文件&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红队评估实战靶场(四)

靶机链接&#xff1a;http://vulnstack.qiyuanxuetang.net/vuln/detail/6/ 环境搭建 新建两张仅主机网卡&#xff0c;一张192.168.183.0网段&#xff08;内网网卡&#xff09;&#xff0c;一张192.168.157.0网段&#xff08;模拟外网网段&#xff09;&#xff0c;然后按照拓补…...

Android Studio 历史版本下载

Android Studio 历史版本下载 官方链接&#xff1a;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 部署与管理指南:简化前端应用的自动化部署流程

引言 在现代的前端开发中&#xff0c;部署和托管项目一直是开发者关注的重要环节。Vercel&#xff0c;作为一个专注于简化前端开发和部署的平台&#xff0c;凭借其强大的自动化功能、全球内容分发网络&#xff08;CDN&#xff09;以及对 Next.js 等框架的优越支持&#xff0c;…...

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)

一、说明 文档比对光靠前端或者后端是无法实现的。 该文中的实现方案为&#xff1a;onlyofficejava。java进行文档差异化比较并输出对比结果&#xff0c;only进行得到结果处理渲染。 此方案目前为Beta版本&#xff0c;简单Word Demo实现了比对结果。css、关联动态效果登将在后期…...

JS querySelector方法的优点

1. 灵活性 支持所有 CSS 选择器 ID 选择器&#xff1a;#id 示例&#xff1a;document.querySelector(#myId)解释&#xff1a;选择 id 为 myId 的元素。类选择器&#xff1a;.class 示例&#xff1a;document.querySelector(.myClass)解释&#xff1a;选择具有 class 为 myCla…...

利用获取商品详情API:item_get可以获取到淘宝商品详情的哪些数据?

先来看下测试的返回数据吧 items: { total_results: 76, totalpage: 8, page_size: 10, page: "1", item: [ { rate_content: "和我家的鞋柜特别搭&#xff0c;加上这一条遮挡布&#xff0c;感觉整洁多了&#xff0c;布料不是硬邦邦的那种&#xff0c;很满意。…...

【大数据学习 | 面经】Spark 3.x 中的AQE(自适应查询执行)

Spark 3.x 中的自适应查询执行&#xff08;Adaptive Query Execution&#xff0c;简称 AQE&#xff09;通过多种方式提升性能&#xff0c;主要包括以下几个方面&#xff1a; 动态合并 Shuffle 分区&#xff08;Coalescing Post Shuffle Partitions&#xff09;&#xff1a; 当 …...

[Vue]Vue-router

路由 对前端路由的理解 在前端技术早期&#xff0c;一个 url 对应一个页面&#xff0c;如果要从 A 页面切换到 B 页面&#xff0c;那么必然伴随着页面的刷新。这个体验并不好&#xff0c;不过在最初也是无奈之举——用户只有在刷新页面的情况下&#xff0c;才可以重新去请求数…...

【HarmonyOS】鸿蒙应用使用lottie动画

【HarmonyOS】鸿蒙应用使用lottie动画 一、lottie动画是什么&#xff1f; https://airbnb.design/lottie Lottie是由Airbnb团队开发的一个适用于iOS、Android、React Native、Web和Windows的开源动画库&#xff0c;用于解析使用Bodymovin导出为JSON的Adobe After Effects动…...

1.使用docker 部署redis Cluster模式 集群3主3从

1.使用docker 部署redis Cluster模式 集群3主3从 1.1 先安装docker 启动docker服务&#xff0c;拉取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博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…...

Luban数据插件的用法

配置后数据后&#xff0c;点击图1中的gen.bat文件启动生成配置数据和解析配置数据代码的程序&#xff0c;自动生成配置数据和解析用到的代码&#xff1b;因为我已经 指定了生成内容的输出路径为Unity项目的路径下面&#xff0c;所以&#xff0c;不用再搬运生成的内容到项目目录…...

指针(上)

目录 内存和地址 指针变量和地址 取地址&#xff08;&&#xff09; 解引用&#xff08;*&#xff09; 大小 类型 意义 const修饰 修饰变量 修饰指针 指针运算 指针- 整数 指针-指针 指针的关系运算 野指针 概念 成因 避免 assert断言 指针的使用 strl…...

张伟楠动手学强化学习笔记|第一讲(上)

张伟楠动手学强化学习笔记|第一讲&#xff08;上&#xff09; 人工智能的两种任务类型 预测型任务 有监督学习无监督学习 决策型任务 强化学习 序贯决策(Sequential Decision Making) 智能体序贯地做出一个个决策&#xff0c;并接续看到新的观测&#xff0c;知道最终任务结…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...