【C++动态规划】2435. 矩阵中和能被 K 整除的路径|1951

本文涉及知识点

C++动态规划

LeetCode2435. 矩阵中和能被 K 整除的路径

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发,每一步只能往 下 或者往 右 ,你想要到达终点 (m - 1, n - 1) 。
请你返回路径和能被 k 整除的路径数目,由于答案可能很大,返回答案对 109 + 7 取余 的结果。
示例 1:
在这里插入图片描述

输入:grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出:2
解释:有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径,和为 5 + 2 + 4 + 5 + 2 = 18 ,能被 3 整除。
第二条路径为上图中用蓝色标注的路径,和为 5 + 3 + 0 + 5 + 2 = 15 ,能被 3 整除。
示例 2:
在这里插入图片描述

输入:grid = [[0,0]], k = 5
输出:1
解释:红色标注的路径和为 0 + 0 = 0 ,能被 5 整除。
示例 3:

在这里插入图片描述

输入:grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出:10
解释:每个数字都能被 1 整除,所以每一条路径的和都能被 k 整除。

提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 5 * 104
1 <= m * n <= 5 * 104
0 <= grid[i][j] <= 100
1 <= k <= 50

动态规划

动态规划的状态表示

dp[r][c][k] 记录从起点到达(r,c) 路径和%K == k的方案数。空间复杂度:O(mnk)

动态规划的转移方程

枚举前置状态(r,c,k)
(r1,c1)是(r+1,c)或(r,c+1)
dp[r1][c1][(k+grid[r1][c1])%K] += dp[r][c][k]
单个状态转移的时间复杂度是:O(1),** 总复杂度**:O(mnk)

动态规划的填表顺序

先行后列,行号和列号都从小到大。
由于只能下移,不能上移,所以行号小的一定是前置节点。由于只能右移,不能左移,所以行号相同,列号小的是前置节点。

动态规划的初始值

全部为0。

动态规划的返回值

dp.back().back()[0]

代码

核心代码


template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}C1097Int  operator/(const C1097Int& o)const{return *this * o.PowNegative1();}C1097Int& operator/=(const C1097Int& o){*this /= o.PowNegative1();return *this;}bool operator==(const C1097Int& o)const{return m_iData == o.m_iData;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};class Solution {public:int numberOfPaths(vector<vector<int>>& grid, int K) {const int R = grid.size();const int C = grid[0].size();vector<vector<vector<C1097Int<>>>> dp(R, vector<vector<C1097Int<>>>(C, vector<C1097Int<>>(K)));dp[0][0][grid[0][0] % K] = 1;for (int r = 0; r < R; r++) {for (int c = 0; c < C; c++) {for (int k = 0; k < K; k++) {if (r + 1 < R) {dp[r + 1][c][(k + grid[r + 1][c]) % K] += dp[r][c][k];}if (c + 1 < C) {dp[r][c + 1][(k + grid[r][c + 1]) % K] += dp[r][c][k];}}}}return dp.back().back()[0].ToInt();}};

单元测试

vector<vector<int>> grid;int k;TEST_METHOD(TestMethod11){grid = { {5,2,4},{3,0,5},{0,7,2} }, k = 3;auto res = Solution().numberOfPaths(grid, k);AssertEx(2, res);}TEST_METHOD(TestMethod12){grid = { {0,0} }, k = 5;auto res = Solution().numberOfPaths(grid, k);AssertEx(1, res);}TEST_METHOD(TestMethod13){grid = { {7,3,4,9},{2,3,6,2},{2,3,7,0} }, k = 1;auto res = Solution().numberOfPaths(grid, k);AssertEx(10, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【QT】Qt对话框

个人主页~ Qt窗口属性~ Qt窗口 五、对话框2、Qt内置对话框&#xff08;1&#xff09;Message Box&#xff08;2&#xff09;QColorDialog&#xff08;3&#xff09;QFileDialog&#xff08;4&#xff09;QFontDialog&#xff08;5&#xff09;QInputDialog 五、对话框 2、Qt内…

视频推荐的算法(字节青训)

题目&#xff1a; 西瓜视频 正在开发一个新功能&#xff0c;旨在将访问量达到80百分位数以上的视频展示在首页的推荐列表中。实现一个程序&#xff0c;计算给定数据中的80百分位数。 例如&#xff1a;假设有一个包含从1到100的整数数组&#xff0c;80百分位数的值为80&#…

线程基础知识、jmm(Java内存模型)

目录 线程基础知识 并发与并行 进程和线程 线程优先级 创建线程的方式主要有三种 休眠 作出让步 join() 方法 线程协作注意什么 理解线程状态 选择合适的协作工具 共享资源的访问控制 避免竞争条件 创建线程几种方式 线程状态&#xff0c;状态之间切换 新建&…

2.数组越界访问如何调试HardFault错误

数组越界 在项目开发过程中&#xff0c;配置串口外设是一个常见的任务&#xff0c;但在实际操作中&#xff0c;我们可能会遇到一些预料之外的问题。例如&#xff0c;在调试过程中&#xff0c;我们发现单片机只接受了一次数据后便不再接收&#xff0c;这无疑是一个棘手的问题。…

0-ARM Linux驱动开发-字符设备

一、字符设备概述 Linux 系统中&#xff0c;设备被分为字符设备、块设备和网络设备等。字符设备以字节流的方式进行数据传输&#xff0c;数据的访问是按顺序的&#xff0c;一个字节一个字节地进行读取和写入操作&#xff0c;没有缓冲区。例如&#xff0c;终端&#xff08;/dev…

openGauss数据库-头歌实验1-4 数据库及表的创建

一、创建数据库 &#xff08;一&#xff09;任务描述 本关任务&#xff1a;创建指定数据库。 &#xff08;二&#xff09;相关知识 数据库其实就是可以存放大量数据的仓库&#xff0c;学习数据库我们就从创建一个数据库开始吧。 为了完成本关任务&#xff0c;你需要掌握&a…

深入浅出 Spring Boot 与 Shiro:构建安全认证与权限管理框架

一、Shiro框架概念 &#xff08;一&#xff09;Shiro框架概念 1.概念&#xff1a; Shiro是apache旗下一个开源安全框架&#xff0c;它对软件系统中的安全认证相关功能进行了封装&#xff0c;实现了用户身份认证&#xff0c;权限授权、加密、会话管理等功能&#xff0c;组成一…

重学SpringBoot3-整合 Elasticsearch 8.x (一)客户端方式

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 这里写目录标题 1. 为什么选择 Elasticsearch&#xff1f;2. Spring Boot 3 和 Elasticsearch 8.x 的集成概述2.1 准备工作2.2 添加依赖 3. Elasticsearch 客户端配置方式…

MyBaitsPlus 基本用法简单整理

MyBaitsPlus 基本用法整理 查询单表查询查询单条数据写法一&#xff1a;&#xff08;this.getOne&#xff09;写法二&#xff1a;&#xff08;XxxMapper.selectById&#xff09;写法三&#xff1a;&#xff08;this.getById&#xff09; 查询 list 集合&#xff08;this.list&a…

基于MATLAB的战术手势识别

手势识别的研究起步于20世纪末&#xff0c;由于计算机技术的发展&#xff0c;特别是近年来虚拟现实技术的发展&#xff0c;手势识别的研究也到达一个新的高度。熵分析法是韩国的李金石、李振恩等人通过从背景复杂的视频数据中分割出人的手势形状&#xff0c;然后计算手型的质心…

Mac 配置SourceTree集成云效

1、背景 工作使用的是自己的笔记本&#xff0c;一个是比较卡&#xff0c;在一个是敏感信息比较多还是使用公司的电脑&#xff0c;但是系统是Mac就很麻烦&#xff0c;在网上找了帖子记录一下 2、配置 打开终端 ssh-keygen -t rsa #一直回车就行 cd .ssh cat id_rsa.pub #查…

【快速上手】pyspark 集群环境下的搭建(Yarn模式)

目录 前言&#xff1a; 一、安装步骤 安装前准备 1.第一步&#xff1a;安装python 2.第二步&#xff1a;在bigdata01上安装spark 3.第三步&#xff1a;同步bigdata01中的spark到bigdata02和03上 二、启动 三、可打开yarn界面查看任务 前言&#xff1a; 上一篇介绍的是…

使用Python多线程抓取某图网数据并下载图片

前言 在互联网开发领域&#xff0c;数据抓取是一项非常实用的技术。通过数据抓取&#xff0c;我们可以从网页上获取所需的信息&#xff0c;并将其转化为结构化数据&#xff0c;以便进一步分析或使用。本文将介绍如何利用Python编写一个多线程程序来抓取网页上的图片数据&#…

《IMM交互式多模型滤波MATLAB实践》专栏目录,持续更新……

专栏链接&#xff1a;https://blog.csdn.net/callmeup/category_12816762.html 专栏介绍 关于IMM的例程 双模型EKF&#xff1a; 【逐行注释】基于CV/CT模型的IMM|MATLAB程序|源代码复制后即可运行&#xff0c;无需下载三模型EKF&#xff1a; 【matlab代码】3个模型的IMM例程&…

鸿蒙开发案例:指南针

【1】引言&#xff08;完整代码在最后面&#xff09; 在本文中&#xff0c;我们将介绍如何使用鸿蒙系统&#xff08;HarmonyOS&#xff09;开发一个简单的指南针应用。通过这个案例&#xff0c;你可以学习如何使用传感器服务、状态管理以及UI构建等基本技能。 【2】环境准备 …

人工智能的发展与未来:从Yann LeCun的观点谈起

引言 在当今的人工智能&#xff08;AI&#xff09;领域&#xff0c;AGI&#xff08;通用人工智能&#xff09;已成为热门话题。许多专家认为&#xff0c;随着技术的不断发展&#xff0c;AGI的实现只是时间问题。然而&#xff0c;Yann LeCun——图灵奖得主、Meta首席AI科学家&a…

【The Art of Unit Testing 3_自学笔记06】3.4 + 3.5 单元测试核心技能之:函数式注入与模块化注入的解决方案简介

文章目录 3.4 函数式依赖注入技术 Functional injection techniques3.5 模块化依赖注入技术 Modular injection techniques 写在前面 上一篇的最后部分对第三章后续内容做了一个概括性的梳理&#xff0c;并给出了断开依赖项的最简单的实现方案&#xff0c;函数参数值注入法。本…

电磁兼容(EMC):整改案例(六)Y电容过大导致雷击浪涌炸机

目录 1. 异常现象 2. 原因分析 3. 整改方案 4. 总结 1. 异常现象 某金属外壳带接地线的产品按GB/T 17626.5进行雷击浪涌测试&#xff0c;在L&#xff0c;N线对PE进行4kV浪涌电压测试时&#xff0c;出现炸机现象&#xff0c;AC-DC电源芯片损坏。而在L&#xff0c;N线间进行2…

代码之眼,陈欣的xml解密之路

第一章 在未来的世界里&#xff0c;科技已经发展到了令人难以想象的地步。人工智能、量子计算和生物技术交织在一起&#xff0c;创造了一个全新的社会形态。在这个世界中&#xff0c;有一个名为“代码守护者”的组织&#xff0c;专门负责维护全球信息系统的安全和稳定。 陈欣是…

L0G1000:Linux+InternStudio 闯关作业

1. 配置基础环境 首先&#xff0c;打开 Intern Studio 界面&#xff0c;点击 创建开发机 配置开发机系统。 InternStudio 填写 开发机名称 后&#xff0c;点击 选择镜像 使用 Cuda11.7-conda 镜像&#xff0c;然后在资源配置中&#xff0c;使用 10% A100 * 1 的选项&#xff…