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].length1 <= 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 题目描述: 实现代码与解析: 动态规划 原理思路: 1289. 下降路径最小和 II 题目描述: 给你一个 n x n 整数矩阵 grid ,请你返回 非零偏移下降路径 数字和的最小值。 非零偏移下降路…...
Node.js |(一)Node.js简介及计算机基础 | 尚硅谷2023版Node.js零基础视频教程
学习视频:尚硅谷2023版Node.js零基础视频教程,nodejs新手到高手 文章目录 📚关于Node.js🐇为什么要学Node.js🐇Node.js是什么🐇Node.js的作用🐇Node.js下载安装🐇命令行工具…...
Canal+Kafka实现Mysql数据同步
Canal介绍 canal [kənl],译意为水道/管道/沟渠,主要用途是基于 MySQL 数据库增量日志解析,提供增量数据订阅和消费 canal可以用来监控数据库数据的变化,从而获得新增数据,或者修改的数据。 canal是应阿里巴巴存在杭…...
K8s部署
K8s部署 一、实验架构 二进制搭建 Kubernetes v1.20 -单master节点部署k8s集群master01:192.168.111.10 kube-apiserver kube-controller-manager kube-scheduler etcd k8s集群master02:192.168.111.20k8s集群node01:192.168.111.20 kubele…...
MongoDB 分片集群
在了解分片集群之前,务必要先了解复制集技术! 1.1 MongoDB复制集简介 一组Mongodb复制集,就是一组mongod进程,这些进程维护同一个数据集合。复制集提供了数据冗余和高等级的可靠性,这是生产部署的基础。 1.1.1 复制集…...
CSDN 编程竞赛六十九期题解
竞赛总览 CSDN 编程竞赛六十九期:比赛详情 (csdn.net) 竞赛题解 题目1、S数 如果一个正整数自身是回文数,而且它也是一个回文数的平方,那么我们称这个数为S数。现在,给定两个正整数L、R,返回包含在范围 [L, R] 中S…...
vue3组合式api单文件组件写法
一,模板部分 <template><div class"device container"><breadcrumb :list"[首页, 应急处置]" /><div class"search_box"><div class"left"><span style"margin-right: 15px"…...
Unity游戏源码分享-多角色fps射击游戏
Unity游戏源码分享-多角色fps射击游戏 项目地址:https://download.csdn.net/download/Highning0007/88204023...
在Cesium中给管道添加水流效果
添加效果前后对比: 关键代码: /*** 水流粒子,目前支持向上或者向下的效果* 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 传统的代码架构模式,仅仅是对代码进行了分层,其中的C代表Controller,控制的意思 将代码划分为数据层,视图层,控制层,三层之间可以任意交互 MVP MVP是在MVC基础上改进而来的一种架构,其中的…...
代码质量检查工具SonarQube
Devops流水线之SonarQube 文章目录 Devops流水线之SonarQube1. 软件功能介绍及用途2. 软件环境搭建与使用2.1 使用方法2.2 SonarQube相关属性说明2.3 Sonar配置文件内容说明 3. 使用环节4. 检查方法 1. 软件功能介绍及用途 SonarQube是一个用于代码质量管理的开源平台…...
开发命名规范
1项目命名规范 1、工程项目名,尽量想一些有意义、有传播价值的名称;比如星球、游戏、名人、名地名等;取名就跟给孩子取名一样,独特、有价值、有意义、好传播 2、所有的类都必须添加创建者和创建日期 3、所有代码:包括…...
12. Redis分布式高可用集群搭建
文章目录 Redis分布式高可用集群搭建一、redis集群有三种方式:1. 主从模式2. 哨兵3. 集群(master-cluster) 二、基于centos7操作系统操做1. 关闭防火墙,三台机器都执行2. hostname修改,三台机器都执行,这一步是为了在内…...
【微信小程序篇】-请求封装
最近自己在尝试使用AIGC写一个小程序,页面、样式、包括交互函数AIGC都能够帮我完成(不过这里有一点问题AIGC的上下文关联性还是有限制,会经常出现对于需求理解跑偏情况,需要不断的重复强调,并纠正错误,才能得到你想要的…...
区块链-Web3.0-什么是Web3.0?
一、什么是Web 3.0 Web 3.0,也被称为“去中心化Web”或“智能Web”,是互联网的下一代,它使用了分布式系统技术、区块链技术和智能合约等新型技术,旨在构建一个更加去中心化、安全、透明和智能的互联网。Web 3.0 可以带来更广泛的…...
动手学深度学习(三)线性神经网络—softmax回归
分类任务是对离散变量预测,通过比较分类的概率来判断预测的结果。 softmax回归和线性回归一样也是将输入特征与权重做线性叠加,但是softmax回归的输出值个数等于标签中的类别数,这样就可以用于预测分类问题。 分类问题和线性回归的区别&#…...
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 相关网站整理大全 众所周知,工欲善其事必先利其器,有一个好的工具可以让我们事半功倍,有一个好用的网站更是如此! 但是好用的网站真的太多了,收藏夹都满满的(但是几乎没打开用过😁)。 所以本文是对…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...
C++--string的模拟实现
一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现,其目的是加强对string的底层了解,以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量,…...
DeepSeek越强,Kimi越慌?
被DeepSeek吊打的Kimi,还有多少人在用? 去年,月之暗面创始人杨植麟别提有多风光了。90后清华学霸,国产大模型六小虎之一,手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水,单月光是投流就花费2个亿。 疯…...
