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

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...