当前位置: 首页 > 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;)。 所以本文是对…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...

【学习记录】使用 Kali Linux 与 Hashcat 进行 WiFi 安全分析:合法的安全测试指南

文章目录 &#x1f4cc; 前言&#x1f9f0; 一、前期准备✅ 安装 Kali Linux✅ 获取支持监听模式的无线网卡 &#x1f6e0; 二、使用 Kali Linux 进行 WiFi 安全测试步骤 1&#xff1a;插入无线网卡并确认识别步骤 2&#xff1a;开启监听模式步骤 3&#xff1a;扫描附近的 WiFi…...

【JavaEE】万字详解HTTP协议

HTTP是什么&#xff1f;-----互联网的“快递小哥” 想象我们正在网上购物&#xff1a;打开淘宝APP&#xff0c;搜索“蓝牙耳机”&#xff0c;点击商品图片&#xff0c;然后下单付款。这一系列操作背后&#xff0c;其实有一个看不见的“快递小哥”在帮我们传递信息&#xff0c;…...