lintcode 567 · 最大得分 【动态规划 中等 】
题目
https://www.lintcode.com/problem/567
给定一个矩阵matrix,
matrix[i][j]表示你到达第i行第j列可以得到的分数,现在你要用第0行任意一点出发,从每行里找到一个点进行跳跃,每次从(i,j)到(i+1,k)跳跃需要消耗∣j−k∣的分数,请问到最后一行以后,你最多可以得到多少分。1≤len(matrix),len(matrix[0])≤1000≤matrix[i][j]≤10 ^5样例
样例 1输入:
[[1, 2],[3, 4]]
输出: 6
说明 2 + 4 = 6.
思路
动态规划,下一行依赖上一行
答案
public class Solution {/*** @param matrix: the matrix* @return: the maximum score you can get*/public int maximumScore(int[][] matrix) {//简单的动态规划,认真读题目,看下面的代码//很容易看懂依赖关系int n = matrix.length,m=matrix[0].length;int[][] dp = new int[n][m];for (int j = 0; j < m ; j++) {dp[0][j] = matrix[0][j];}for (int i = 1; i <n ; i++) {for (int j = 0; j <m ; j++) {for (int k = 0; k <m ; k++) {dp[i][j] = Math.max(dp[i][j],dp[i-1][k]-Math.abs(j-k)+matrix[i][j]);}}}int max =Integer.MIN_VALUE;for (int i = 0; i < m; i++) {max=Math.max(max,dp[n-1][i]);}return max;}
}
相关文章:
lintcode 567 · 最大得分 【动态规划 中等 】
题目 https://www.lintcode.com/problem/567 给定一个矩阵matrix, matrix[i][j]表示你到达第i行第j列可以得到的分数,现在你要用第0行任意一点出发,从每行里找到一个点进行跳跃,每次从(i,j)到(i1,k)跳跃需要消耗∣j−k∣的分数&…...
qml嵌入到QWidget的两种方式介绍
本文介绍qml页面嵌入到QWidget的两种方式,以及这两种方式的区别。 方式1 在 Qt 中,可以使用 QQuickWidget 将 QML 内容嵌入到基于 QWidget 的应用程序中。这是在旧的 QWidget-based 应用程序中逐渐引入 QML UI 的一种常见方式。 以下是如何使用 QQuickWidget 将 QML 内容嵌…...

Mysql数据库之常用SQL语句及事务学习总结
数据库介绍 几个常见的缩写: DB:数据库。全称:DataBase。DBMS:数据库管理系统。全称:DataBase Management System。DBS:数据库系统。全称:DataBase System。DBA:数据库管理员。全称…...

RuoYi若依管理系统最新版 基于SpringBoot的权限管理系统
RuoYi是一个后台管理系统,基于经典技术组合(Spring Boot、Apache Shiro、MyBatis、Thymeleaf)主要目的让开发者注重专注业务,降低技术难度,从而节省人力成本,缩短项目周期,提高软件安全质量。 本…...

html实现邮件模版布局-flex布局table布局-demo
邮件模版布局 flex - 布局简单方便 兼容性差 table - 优点 就是兼容性好,其他没有优点 注:使用图片需要png最好,使用svg图google邮箱会出现不能使用的情况 效果图 flex布局 <!DOCTYPE html> <html lang"en" xmlns:th&qu…...
CENTOS7安装redis在/home/pms/software路径下,并且将redis加入到systemctl中
要将/home/software/redis-stack-server-7.2.0-v0/service/redis.service添加到systemctl系统管理,你可以执行以下步骤: 创建软连接: sudo ln -s /home/software/redis-stack-server-7.2.0-v0/service/redis.service /etc/systemd/system/r…...
数据库笔记
数据库原理及应用 半期考:运筹学,概率论,数据库 文章目录 数据库原理及应用1.课程的考核2.数据库的运用3.数据库学什么? 第一章 绪论1.1数据库系统概述1.1.1基本概念1.1.2数据管理技术的生产和发展人工管理文件系统数据库系统 1.…...

AI是风口还是泡沫?
KlipC报道:狂热的人工智能追捧潮有所冷静,投资者在“上头”的追涨之后,开始回归到对基本面的关注。 KlipC的合伙人Andi D表示:“近日,有关英伟达二季度“破纪录”财报涉嫌造假的话题正在社交媒体和投资者论坛中甚嚣尘上…...

echarts环图配置
echarts环图配置 1、安装echarts npm install echarts4.9.02、页面引入echarts import echarts from echarts;3、应用 template片段 <div class"chart-wrap"><div id "treeChart" style "width: 180px; height:180px;" ><…...

Redis优化 RDB AOF持久化
---------------------- Redis 高可用 ---------------------------------------- 在web服务器中,高可用是指服务器可以正常访问的时间,衡量的标准是在多长时间内可以提供正常服务(99.9%、99.99%、99.999%等等)。 但是在Redis语境…...

三维模型3DTILE格式轻量化压缩主要技术方法浅析
三维模型3DTILE格式轻量化压缩主要技术方法浅析 三维模型3DTILE格式轻量化压缩主要技术方法浅析 随着三维地理空间数据的应用日益广泛,为了更快速地传输和存储这些大规模数据,3DTile格式的轻量化压缩显得尤为重要。本文将浅析关于三维模型3DTile格式轻量…...

c++day2---9.7
1> 思维导图 2> 封装一个结构体,结构体中包含一个私有数组,用来存放学生的成绩,包含一个私有变量,用来记录学生个数, 提供一个公有成员函数,void setNum(int num)用于设置学生个数 提供一个公有成员…...

地震反演基础知识2(代码演示)
文章目录 数据集代码演示1. SEG盐真实数据2. SEG盐速度模型3. SEG盐模拟地震数据4. SEG盐模拟速度模型5. openfwi地震数据6. openfwi速度模型 数据集代码演示 1. SEG盐真实数据 # 绘制SEG盐层数据的地震图像 def pain_seg_seismic_data(para_seismic_data):Plotting seismic …...

C#学习 - 方法的定义、调用、调试
方法 方法(Method)是由C/C中的函数(Function)发展而来的 //C语言 #include <stdio.h> int Add(int x, int y) {return x y; }//函数 int main(void) {int a 4;int b 2;int c Add(a, b);printf("%d %d %d\n&quo…...

『PyQt5-Qt Designer篇』| 09 Qt Designer中分割线和间隔如何使用?
09 Qt Designer中分割线和间隔如何使用? 1 间隔1.1 水平间隔1.2 垂直间隔2 分割线2.1 水平线2.2 垂直线3 保存并执行1 间隔 间隔有水平间隔和垂直间隔: 1.1 水平间隔 拖动4个按钮,并设置为水平布局: 在第一个按钮的右边添加一个水平间隔: 设置其sizeType为Fixed,宽度为20…...

基于springboot2+mybatis-plus+jsp增删改查
概述 编写简单增删改查,理解之后可以自己试着扩展,相信你也可以,加油,我自己懂了的用注释记在下面方便理解 详细 一、需求(要做什么) 基于现今最流行的技术实现增删改查demo, 便于初学者上手…...
[PHP]empty一直返回true
class Post {public function __get($key){return true;} }$post new Post(); var_dump(empty($post->a));// bool(true) PHP: 重载 - Manual 读取不可访问(protected 或 private)或不存在的属性的值时,__get() 会被调用。 当对不可访…...
[2023.09.11]: Yew的SSR中的Cargo.toml配置
由于各种原因,我最后还是打算把Yew应用的开发从csr模式转成ssr模式。没想到这里面的水还是挺深的,这里面的Cargo.toml配置包含的信息量之大,着实让我头疼了一番。 Cargo.toml的配置如下 [package] name "app" version "0.…...
HTTPS加密协议详解:HTTPS性能与优化
1、HTTPS性能损耗 前文讨论了HTTPS原理与优势:身份验证、信息加密与完整性校验等,且未对TCP和HTTP协议做任何修改。但通过增加新协议以实现更安全的通信必然需要付出代价,HTTPS协议的性能损耗主要体现如下: (1).增加延时 分析前…...
9月11日,每日信息差
今天是2023年09月11日,以下是为您准备的13条信息差 第一、微软已停止向俄罗斯提供服务,俄罗斯接下来的举动震惊世人!对此俄罗斯回应称,他们将把微软的收费版改为免费版并推广至全球 第二、我国首套海洋漂浮式温差能发电装置完成…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...

9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...

jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析
1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器(TI)推出的一款 汽车级同步降压转换器(DC-DC开关稳压器),属于高性能电源管理芯片。核心特性包括: 输入电压范围:2.95V–6V,输…...