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

DeerFlow进阶教程:集成MCP服务扩展AI助手能力实战

DeerFlow进阶教程&#xff1a;集成MCP服务扩展AI助手能力实战 1. 引言 1.1 为什么需要MCP服务集成 在AI助手领域&#xff0c;单一模型的能力往往难以满足复杂任务需求。DeerFlow作为深度研究助理&#xff0c;通过集成MCP&#xff08;Multi-Component Platform&#xff09;服…...

Idiap研究院:让语音识别AI学会聆听对话历史,压缩音频记忆

语音识别技术在我们的生活中越来越常见&#xff0c;从手机语音助手到客服电话&#xff0c;从会议记录到智能搜索。但你有没有想过&#xff0c;为什么这些系统有时候会犯一些很明显的错误&#xff1f;比如当你在和语音助手对话时&#xff0c;明明在前一句话中提到了"张三&q…...

OpenClaw多模型混搭方案:Kimi-VL-A3B-Thinking与Qwen3-32B协同工作流

OpenClaw多模型混搭方案&#xff1a;Kimi-VL-A3B-Thinking与Qwen3-32B协同工作流 1. 为什么需要多模型混搭&#xff1f; 去年冬天&#xff0c;当我第一次尝试用OpenClaw处理图文混排的文档时&#xff0c;遇到了一个尴尬的问题&#xff1a;纯文本模型Qwen3-32B对图片内容视而不…...

这本《大语言模型》直接封神,清华张亚勤盛赞“入门圣经”,A100集群训练日志全公开!

《大语言模型》由赵鑫教授领衔&#xff0c;系统拆解大语言模型全流程&#xff0c;含预训练、微调、部署等核心内容&#xff0c;并曝光“毒数据”识别技巧。书中案例支持端到端复现&#xff0c;配套YuLan大模型和LLMBox工具库&#xff0c;适合入门学习。当DeepSeek开出11w*14薪抢…...

Embree 4.4.0完全指南:终极光线追踪性能优化方案 [特殊字符]

Embree 4.4.0完全指南&#xff1a;终极光线追踪性能优化方案 &#x1f680; 【免费下载链接】embree Embree ray tracing kernels repository. 项目地址: https://gitcode.com/gh_mirrors/em/embree Embree 4.4.0是Intel开发的高性能光线追踪内核库的最新版本&#xff0…...

LiquidPrompt性能优化终极指南:让你的Shell提示符运行如飞

LiquidPrompt性能优化终极指南&#xff1a;让你的Shell提示符运行如飞 【免费下载链接】liquidprompt A full-featured & carefully designed adaptive prompt for Bash & Zsh 项目地址: https://gitcode.com/gh_mirrors/li/liquidprompt LiquidPrompt是一个功能…...

欧姆龙CP1H+CIF11与施耐德ATV变频器通讯程序 功能:原创程序,可直接用于现场程序

欧姆龙CP1HCIF11与施耐德ATV变频器通讯程序 功能&#xff1a;原创程序&#xff0c;可直接用于现场程序。 欧姆龙CP1H的CIF11通讯板&#xff0c;实现对施耐德ATV12变频器 设定频率&#xff0c;读取实际频率&#xff0c;变频器状态功能。 反应灵敏&#xff0c;通讯稳定可靠。 非常…...

Swin2SR部署优化:FP16量化+TensorRT加速使推理速度提升3.2倍教程

Swin2SR部署优化&#xff1a;FP16量化TensorRT加速使推理速度提升3.2倍教程 你是不是也遇到过这种情况&#xff1a;手头有一张特别喜欢的图片&#xff0c;但分辨率太低&#xff0c;放大后全是马赛克&#xff0c;根本没法用&#xff1f;或者用AI生成的图片细节很棒&#xff0c;…...

Mysql的行级锁到底是怎么加的?匦

1. 架构背景与演进动力 1.1 从单体到碎片化&#xff1a;.NET 的开源征程 在.NET Framework 时代&#xff0c;构建系统主要围绕 Windows 操作系统紧密集成&#xff0c;采用传统的封闭式开发模式。然而&#xff0c;随着.NET Core 的推出&#xff0c;微软开启了彻底的开源与跨平台…...

深入剖析 Android 系统属性:从 build.prop 到 Selinux 安全机制

1. Android系统属性基础入门 第一次接触Android系统属性时&#xff0c;我也被各种.prop文件和复杂的配置搞得一头雾水。经过多年实战&#xff0c;我发现理解属性系统其实有个简单的方法 - 把它想象成Windows的注册表。就像注册表存储着Windows的配置信息一样&#xff0c;Androi…...