3122.使矩阵满足条件的最少操作次数

周赛第三题,知道要用动态规划,但是不知道怎么回到子问题

        显然根据题意我们需要让每一列都相同,但是相邻列不能选择同一种数字,观察到数据nums[i]介于0-9,我们就以此为突破口.

        首先我们用count[n][10], count[i][j]记录第i+1列值为j的元素个数,转移方程如下:

dfs(i,pre) = max(dfs(i-1,k) + count[i][k])   k=0,1...9  k!=pre;

表示 i 对应的那一列选择k的话, 再去判断i-1对应的那一列的元素

        入口是dfs(n-1,10); 使用10是表示没有上一个,取0-9均可

代码如下: 这里写的是 记忆化回溯 ,可以自行改成二维dp

class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int count[n][10]; //count[i][j] 表示 第i+1列里面值等于j的个数
        memset(count,0,sizeof(count));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                count[j][grid[i][j]]++;
            }
        } 
        int memo[n][11];
        memset(memo,-1,sizeof(memo));
        function<int(int,int)> dfs=[&](int i,int pre){  
            if(i==-1) return 0;
            int &res=memo[i][pre];
            if(res!=-1) return res;
            int cnt=0;
            for(int j=0;j<10;j++){
                if(j==pre) continue; 
                cnt=max(cnt,dfs(i-1,j)+count[i][j]);//[[1,6,7,3,0,4,1,3,7,5]]
            } 
            return res=cnt;
        };
        return m*n-dfs(n-1,10);
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/578465.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

根据标签最大层面ROI提取原始图像区域

今天要实现的任务是提取肿瘤的感兴趣区域。 有两个文件&#xff0c;一个是nii的原始图像文件&#xff0c;一个是nii的标签文件。 我们要实现的是&#xff1a;在标签文件上选出最大层面&#xff0c;然后把最大层面的ROI映射到原始图像区域&#xff0c;在原始图像上提裁剪出ROI…

6.模板初阶

目录 1.泛型编程 2. 函数模板 2.1 函数模板概念 2.2函数模板格式 2.3 模板的实现 2.4函数模板的原理 2.5 函数模板的实例化 3.类模板 1.泛型编程 我们如何实现一个 交换函数呢&#xff1f; 使用函数重载虽然可以实现&#xff0c;但是有一下几个不好的地方&#xff1a; …

(学习日记)2024.04.26:UCOSIII第五十节:User文件夹函数概览(uC-CPU文件夹)

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…

docker容器技术篇:集群管理实战mesos+zookeeper+marathon(二)

docker集群管理实战mesoszookeepermarathon&#xff08;二&#xff09; 一 实验环境 操作系统&#xff1a;centos7.9 二 基础环境配置以及安装mesos 安装过程请点击下面的链接查看&#xff1a; 容器集群管理实战mesoszookeepermarathon&#xff08;一&#xff09; 三 安装…

WPF 资源基础

动态资源/静态资源 UI代码 <Window x:Class"WpfApp1.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/ex…

leetcode_37.解数独

37. 解数独 题目描述&#xff1a;编写一个程序&#xff0c;通过填充空格来解决数独问题。 数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08;请参考…

我教你如何可翻页电子画册

​电子画册是一种创新的方式&#xff0c;可以将传统的纸质画册转化为数字化的形式&#xff0c;并且具备翻页的功能。它不仅可以提供更好的阅读体验&#xff0c;还可以方便地分享给他人。 1.选择制作工具&#xff1a; 有许多在线平台和软件可以帮助你制作电子画册&#xff0c;比…

海康大华摄像头rtsp在网页中播放

一.项目说明 摄像头视频推流实现 支持rtsp&#xff1b;rtmp; 摄像头在浏览器中播放实现 内包含资源和对于的部署方案 资料中有详细部署资料和对于的api接口&#xff0c;支持二次开发。 二.项目实现效果 三.下载地址 下载地址&#xff1a;http://www.gxcode.top/code

【春 联---turtle海龟画图】

春联 又称"春贴"、"门对"、"对联"&#xff0c;是过年时所贴的红色喜庆元素"年红"中一个种类。它以对仗工整、简洁箱巧的文字描绘美好形象&#xff0c;抒发美好愿 望&#xff0c;是中国特有的文学形式&#xff0c;是华人们过年 的重要习…

pyqt 动态更换表头和数据

目录 pyqt 动态更换表头和数据代码 效果图&#xff1a; pyqt 动态更换表头和数据代码 from PyQt5.QtGui import QColor, QBrush from PyQt5.QtWidgets import QApplication, QTableWidget, QVBoxLayout, QWidget, QPushButton, QTableWidgetItemclass Example(QWidget):def _…

C语言项目实战——扫雷

目录 1.前言 2.完整流程 2.1规划书 2.2代码部分 2.2.1文件的结构设计 2.2.2变量的创建 2.2.3菜单的基本实现 2.2.4初始化期棋盘 2.2.5输出完整棋盘 2.2.6埋雷的实现 2.2.7查询周围雷的数量 2.2.8扫雷的实现 2.2.9完整代码 3.总结 1.前言 哈喽大家好吖&#xff0c;今…

实力认可!盘古信息荣获软件行业五项殊荣,以IMS驱动新质生产力发展

4月24日&#xff0c;第三届中国软件行业协会发展大会在北京盛大召开&#xff0c;众多软件领域的佼佼者齐聚一堂。盘古信息&#xff0c;凭借其卓越的技术实力和创新成果&#xff0c;在这场盛会上荣获“2023年软件行业领军人物”、“2023年软件行业平台软件领军企业”、“2023年软…

线程池嵌套导致的死锁问题

1、背景 有一个报告功能&#xff0c;报告需要生成1个word&#xff0c;6个excel附件&#xff0c;总共7个文件&#xff0c;需要记录报告生成进度&#xff0c;进度字段jd初始化是0&#xff0c;每个文件生成成功进度加1&#xff0c;生成失败就把生成状态置为失败。 更新进度语句&…

Unity打包PC端exe,压缩打包为一个exe文件

目录 一.打包成功 1.打包输出文件 二.压缩输出目录为exe单个文件 1.添加到压缩文件 2.其他设置 1.点击“高级→自压缩选项” 2.修改解压后运行程序 3.设置模式 4.更新 三、生成.exe 一.打包成功 1.打包输出文件 1、一个后缀为 BurstDebugInformation_DoNotShip的文…

ios不兼容Svg Wave的动画的解决方法

近日也是用上了SvgWave&#xff0c;十分的好看 Svg Wave - A free & beautiful gradient SVG wave Generator. 大家感兴趣的也可以了解一下 【场景】 使用SvgWave的Animate&#xff0c;并生成svg代码使用&#xff0c;windows web端、朋友的安卓移动端都能够正常执行动画…

typescript常用方法整理

基础用法 接口简单用法 函数表达式用法 // 函数类型用于表达式函数 // 接收两个参数name和age //函数返回字符串 interface fun {(name: string, age: number): string } let getData: fun getData function (name, age) {console.log(我的姓名是${name},年龄是${age})return…

SSL证书安装失败怎么办?

在互联网时代&#xff0c;SSL&#xff08;Secure Sockets Layer&#xff09;证书已成为保障网站数据传输安全、提升用户信任度的重要工具。然而&#xff0c;在实际操作过程中&#xff0c;SSL证书的安装并非总能一帆风顺&#xff0c;有时会遇到各种导致安装失败的问题。本文将详…

基于KubeAdm搭建多节点K8S集群

环境准备 说明配置系统CentOS 7.x系列CPU4核及以上内存8G及以上机器数量最少两台&#xff08;一主节点一工作节点&#xff09; 安装docker&#xff08;主节点工作节点&#xff09; 先安装yml yum install -y yum-utils device-mapper-persistent-data lvm2设置阿里云镜像 …

工厂物流3d可视化设计有哪些特点及功能亮点

工厂物流3D可视化设计是一种基于三维模型的物流可视化技术&#xff0c;主要用于展示工厂内部的物流运作情况&#xff0c;具有以下特点和功能亮点&#xff1a; 1. 三维模型展示&#xff1a; 工厂物流3D可视化设计通过三维模型展示工厂内部的物流设施和运作情况&#xff0c;可以…

android studio 编译一直显示Download maven-metadata.xml

今天打开之前的项目的时候遇到这个问题:android studio 编译一直显示Download maven-metadata.xml, AI 查询 报错问题&#xff1a;"android studio 编译一直显示Download maven-metadata.xml" 解释&#xff1a; 这个错误通常表示Android Studio在尝试从Maven仓库…