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

Leetcode每日一题:1289. 下降路径最小和 II(2023.8.10 C++)

目录

1289. 下降路径最小和 II

题目描述:

实现代码与解析:

动态规划

原理思路:


1289. 下降路径最小和 II

题目描述:

        给你一个 n x n 整数矩阵 grid ,请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为:从 grid 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。

示例 1:

输入:grid = [[1,2,3],[4,5,6],[7,8,9]]
输出:13
解释:
所有非零偏移下降路径包括:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ,所以答案是 13 。

示例 2:

输入:grid = [[7]]
输出:7

提示:

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • -99 <= grid[i][j] <= 99

实现代码与解析:

动态规划

class Solution {
public:int minFallingPathSum(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<int>> f(n,vector<int>(m, 0x3f3f3f3f));for (int i = 0; i < m; i++)f[0][i] = grid[0][i];for (int i = 1; i < n; i++)for (int j = 0; j < m; j++)for (int k = 0; k < m; k++){if (j == k) continue;f[i][j] = min(f[i][j], f[i - 1][k] + grid[i][j]);}int res = 0x3f3f3f3f;for (int i = 0; i < m; i++)res = min(res, f[n - 1][i]);// for (int i = 0; i < n; i++)// {//     for (int j = 0; j < m; j++)//     {//         cout << f[i][j] << " ";//     }//     cout << endl;// }      return res;}
};

原理思路:

        顶多中等题,难度不应该标困难。

        动态规划,dp数组含义就是到以下标 i, j 为结尾的最小值。数据量很小,其实就是三重暴力循环而已。 

相关文章:

Leetcode每日一题:1289. 下降路径最小和 II(2023.8.10 C++)

目录 1289. 下降路径最小和 II 题目描述&#xff1a; 实现代码与解析&#xff1a; 动态规划 原理思路&#xff1a; 1289. 下降路径最小和 II 题目描述&#xff1a; 给你一个 n x n 整数矩阵 grid &#xff0c;请你返回 非零偏移下降路径 数字和的最小值。 非零偏移下降路…...

Node.js |(一)Node.js简介及计算机基础 | 尚硅谷2023版Node.js零基础视频教程

学习视频&#xff1a;尚硅谷2023版Node.js零基础视频教程&#xff0c;nodejs新手到高手 文章目录 &#x1f4da;关于Node.js&#x1f407;为什么要学Node.js&#x1f407;Node.js是什么&#x1f407;Node.js的作用&#x1f407;Node.js下载安装&#x1f407;命令行工具&#x1…...

Canal+Kafka实现Mysql数据同步

Canal介绍 canal [kənl]&#xff0c;译意为水道/管道/沟渠&#xff0c;主要用途是基于 MySQL 数据库增量日志解析&#xff0c;提供增量数据订阅和消费 canal可以用来监控数据库数据的变化&#xff0c;从而获得新增数据&#xff0c;或者修改的数据。 canal是应阿里巴巴存在杭…...

K8s部署

K8s部署 一、实验架构 二进制搭建 Kubernetes v1.20 -单master节点部署k8s集群master01&#xff1a;192.168.111.10 kube-apiserver kube-controller-manager kube-scheduler etcd k8s集群master02&#xff1a;192.168.111.20k8s集群node01&#xff1a;192.168.111.20 kubele…...

MongoDB 分片集群

在了解分片集群之前&#xff0c;务必要先了解复制集技术&#xff01; 1.1 MongoDB复制集简介 一组Mongodb复制集&#xff0c;就是一组mongod进程&#xff0c;这些进程维护同一个数据集合。复制集提供了数据冗余和高等级的可靠性&#xff0c;这是生产部署的基础。 1.1.1 复制集…...

CSDN 编程竞赛六十九期题解

竞赛总览 CSDN 编程竞赛六十九期&#xff1a;比赛详情 (csdn.net) 竞赛题解 题目1、S数 如果一个正整数自身是回文数&#xff0c;而且它也是一个回文数的平方&#xff0c;那么我们称这个数为S数。现在&#xff0c;给定两个正整数L、R&#xff0c;返回包含在范围 [L, R] 中S…...

vue3组合式api单文件组件写法

一&#xff0c;模板部分 <template><div class"device container"><breadcrumb :list"[首页, 应急处置]" /><div class"search_box"><div class"left"><span style"margin-right: 15px"…...

Unity游戏源码分享-多角色fps射击游戏

Unity游戏源码分享-多角色fps射击游戏 项目地址&#xff1a;https://download.csdn.net/download/Highning0007/88204023...

在Cesium中给管道添加水流效果

添加效果前后对比&#xff1a; 关键代码&#xff1a; /*** 水流粒子&#xff0c;目前支持向上或者向下的效果* param {Number} x* param {Number} y* param {Number} z* param {Number} options* example* options {* color: Cesium.Color.AZURE,* emissionRate: 5, …...

测试平台——项目模块模型类设计

这里写目录标题 一、项目应用1、项目包含接口:2、创建子应用3、项目模块设计a、模型类设计b、序列化器类设计c、视图类设计d、项目的增删改查操作4、接口模块设计a、模型类设计b、序列化器类设计c、视图类设计d、接口的增删改查查操作5、环境模块设计a、模型类设计b、序列化器…...

【Android】MVC,MVP,MVVM三种架构模式的区别

MVC 传统的代码架构模式&#xff0c;仅仅是对代码进行了分层&#xff0c;其中的C代表Controller&#xff0c;控制的意思 将代码划分为数据层&#xff0c;视图层&#xff0c;控制层&#xff0c;三层之间可以任意交互 MVP MVP是在MVC基础上改进而来的一种架构&#xff0c;其中的…...

代码质量检查工具SonarQube

Devops流水线之SonarQube 文章目录 Devops流水线之SonarQube1. 软件功能介绍及用途2. 软件环境搭建与使用2.1 使用方法2.2 SonarQube相关属性说明2.3 Sonar配置文件内容说明 3. 使用环节4. 检查方法 1. 软件功能介绍及用途 SonarQube是一个用于代码质量管理的开源平台&#xf…...

开发命名规范

1项目命名规范 1、工程项目名&#xff0c;尽量想一些有意义、有传播价值的名称&#xff1b;比如星球、游戏、名人、名地名等&#xff1b;取名就跟给孩子取名一样&#xff0c;独特、有价值、有意义、好传播 2、所有的类都必须添加创建者和创建日期 3、所有代码&#xff1a;包括…...

12. Redis分布式高可用集群搭建

文章目录 Redis分布式高可用集群搭建一、redis集群有三种方式&#xff1a;1. 主从模式2. 哨兵3. 集群&#xff08;master-cluster&#xff09; 二、基于centos7操作系统操做1. 关闭防火墙&#xff0c;三台机器都执行2. hostname修改&#xff0c;三台机器都执行,这一步是为了在内…...

【微信小程序篇】-请求封装

最近自己在尝试使用AIGC写一个小程序&#xff0c;页面、样式、包括交互函数AIGC都能够帮我完成(不过这里有一点问题AIGC的上下文关联性还是有限制&#xff0c;会经常出现对于需求理解跑偏情况&#xff0c;需要不断的重复强调&#xff0c;并纠正错误&#xff0c;才能得到你想要的…...

区块链-Web3.0-什么是Web3.0?

一、什么是Web 3.0 Web 3.0&#xff0c;也被称为“去中心化Web”或“智能Web”&#xff0c;是互联网的下一代&#xff0c;它使用了分布式系统技术、区块链技术和智能合约等新型技术&#xff0c;旨在构建一个更加去中心化、安全、透明和智能的互联网。Web 3.0 可以带来更广泛的…...

动手学深度学习(三)线性神经网络—softmax回归

分类任务是对离散变量预测&#xff0c;通过比较分类的概率来判断预测的结果。 softmax回归和线性回归一样也是将输入特征与权重做线性叠加&#xff0c;但是softmax回归的输出值个数等于标签中的类别数&#xff0c;这样就可以用于预测分类问题。 分类问题和线性回归的区别&#…...

ios swift alert 自定义弹框 点击半透明部分弹框消失

文章目录 1.BaseAlertVC2.BindFrameNumAlertVC 1.BaseAlertVC import UIKitclass BaseAlertVC: GLBaseViewController {let centerView UIView()override func viewDidLoad() {super.viewDidLoad()view.backgroundColor UIColor(displayP3Red: 0, green: 0, blue: 0, alpha:…...

HCIP STP(生成树)

目录 一、STP概述 二、生成树协议原理 三、802.1D生成树 四、STP的配置BPDU 1、配置BPDU的报文格式 2、配置BPDU的工作过程 3、TCN BPDU 4、TCN BPDU的工作过程 五、STP角色选举 1、根网桥选举 2、根端口选举 3、指定端口选举 4、非指定端口选举 六、STP的接口状…...

【Unity开发必备】100多个 Unity 学习网址 资源 收藏整理大全【持续更新】

Unity 相关网站整理大全 众所周知&#xff0c;工欲善其事必先利其器&#xff0c;有一个好的工具可以让我们事半功倍&#xff0c;有一个好用的网站更是如此&#xff01; 但是好用的网站真的太多了&#xff0c;收藏夹都满满的(但是几乎没打开用过&#x1f601;)。 所以本文是对…...

AI技术赋能学术写作,自动目录生成与内容优化,效率飞跃时间节省。

工具对比速览 工具名称 核心功能 处理速度 适用场景 特色优势 aibiye AI降重目录生成 20分钟 学术论文 知网/维普/格子达适配 aicheck AI检测目录优化 实时 初稿检查 多平台规则预判 askpaper 学术规范处理 15-30分钟 期刊投稿 保留专业术语 秒篇 一键式处…...

AI基础设施权力更迭:AWS Bedrock 凭什么在 2026 年让开发者集体“倒戈”?

声明&#xff1a;本文由AI编辑生成&#xff0c;内容仅供参考。文中涉及的行业判断、平台能力分析、商业趋势推演与产品价值描述&#xff0c;均基于公开资料、通用观察及示意性表达整理&#xff0c;不构成任何商业承诺、采购建议、投资建议或服务保证。实际产品能力、接口支持范…...

2026年AI决胜关键: Harness架构才是碾压对手的终极护城河!

文章指出&#xff0c;在AI领域&#xff0c;单纯依靠大模型参数已经无法决定胜负&#xff0c;真正关键的是Harness架构的稳定性。文章通过实证报告揭示&#xff0c;在底层大模型权重不变的情况下&#xff0c;精巧的Harness能使AI通过率大幅提升。文章详细分析了长任务Agent可能面…...

国产发电机转速测控仪的选型有哪些?

一、国科LSK3200-T系列发电机转速信号测控仪LSK3200-T系列转速测控仪外接转速脉冲传感器、电压互感器信号&#xff0c;实时监测水轮发电机组的转速&#xff0c;并在机组各转速点输出开关量信号和与机组转速对应的模拟量信号&#xff0c;为自动开、停机及电厂监控系统服务。仪表…...

OpenEMS:开源能源管理系统的架构解析与应用实践

OpenEMS&#xff1a;开源能源管理系统的架构解析与应用实践 【免费下载链接】openems OpenEMS - Open Source Energy Management System 项目地址: https://gitcode.com/gh_mirrors/op/openems 在可再生能源快速普及的今天&#xff0c;如何高效管理分布式能源系统成为技…...

如何快速解锁百度网盘SVIP下载特权:BaiduNetdiskPlugin-macOS完整教程

如何快速解锁百度网盘SVIP下载特权&#xff1a;BaiduNetdiskPlugin-macOS完整教程 【免费下载链接】BaiduNetdiskPlugin-macOS For macOS.百度网盘 破解SVIP、下载速度限制~ 项目地址: https://gitcode.com/gh_mirrors/ba/BaiduNetdiskPlugin-macOS 还在为百度网盘令人抓…...

15年不上班,我靠什么支撑到现在

我已经12年没去上过班了&#xff0c;14年从学校辞职出来后&#xff0c;就没再给人打过工。虽然我不上班&#xff0c;但身边人都觉得我很会赚钱&#xff0c;觉得我很幸运&#xff0c;也觉得我很有勇气。 其实&#xff0c;并不是我多勇敢&#xff0c;是因为早在2014年&#xff0c…...

书匠策AI:论文写作界的“智能导航仪”,让课程论文创作如行云流水!

在学术的征途中&#xff0c;每一篇课程论文都是一次智慧的探险&#xff0c;既充满挑战也孕育着成长的喜悦。然而&#xff0c;面对浩瀚的知识海洋和复杂的写作规范&#xff0c;许多学子常常感到力不从心&#xff0c;甚至迷失方向。别怕&#xff0c;今天我要为你揭秘一位论文写作…...

财会行业学数据分析的价值分析

数字化转型背景下财会行业的变革需求财会行业正经历从传统核算向数据驱动的转型。企业财务数据量激增&#xff0c;人工处理效率低下&#xff0c;而数据分析能实现自动化处理、实时监控和深度洞察。例如&#xff0c;通过预测模型优化资金配置&#xff0c;或利用可视化工具快速识…...

秒杀系统设计:十万QPS下的技术架构演进

在电商大促场景中&#xff0c;秒杀系统是典型的高并发、低库存业务模型&#xff0c;其核心挑战在于瞬时十万级QPS&#xff08;每秒查询率&#xff09;下的系统稳定性与数据一致性。对于软件测试从业者而言&#xff0c;这不仅涉及性能压测的极限挑战&#xff0c;更需关注架构演进…...