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 相关网站整理大全 众所周知,工欲善其事必先利其器,有一个好的工具可以让我们事半功倍,有一个好用的网站更是如此! 但是好用的网站真的太多了,收藏夹都满满的(但是几乎没打开用过😁)。 所以本文是对…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
