【力扣每日一题】2023.8.17 切披萨的方案数
目录
题目:
示例:
分析:
代码:
题目:
示例:
分析:
题目给我们一个二维数组来表示一个披萨,其中‘A’表示披萨上的苹果。
让我们切k-1刀,把披萨切成 k 份,只能横切或是竖切,最终 k 块披萨都需要拥有有苹果。
问我们一共有几种切披萨的方案。
我的第一反应就是递归去尝试,不过题目有说答案可能会很大,要取余1000000007,那么递归肯定是会超时的,所以我们应该使用动态规划。
因为每次切完披萨,送出去的不是左半边就是上半边,也就是说,披萨的右下角是会一直留下的。因此突破口应该在披萨的右下角,也就是矩阵的右下角。
题目要求每块披萨都需要有至少一个苹果,那么我们就应该要单独去统计一下苹果的分布情况,因为披萨的右下角是会一直留下来的,因此我们可以用一个二维矩阵来存放苹果的分布情况,这个矩阵坐标为 [ i , j ] 的元素就是披萨中 [ i , j ] 位置的右下角中拥有的苹果数。
那么我们初始化这个苹果分布情况数组的时候就应该从右下角开始统计,也就是利用前缀和去统计,递推公式如下,可以参考动图。
apple[i][j] += apple[i+1][j] + apple[i][j+1] - apple[i+1][j+1];
那么统计完了苹果的分布情况有什么用呢,因为要求每次切的披萨都要有苹果,那么我们可以用
apple[i][j1] - apple[i][j2]
知道如果竖切的话,从 j1 到 j2 有没有苹果。用
apple[i1][j] - apple[i2][j]
知道如果横切的话,从 i1 到 i2 有没有苹果。
解决完苹果的问题之后,我们就需要解决切披萨的方案数这个问题了。
由于固定是要切k-1刀,并且本身存放披萨就需要二维数组,因此我们的dp数组就是需要三维。
首先我们先定义dp数组的含义,dp[ i , j , k ]的含义是披萨仅剩从坐标 i , j 开始的右下角部分,并且可以切k刀的方案数。
由于我们可以横切也可以竖切,所以递推公式有两种:
//横切
dp[i1][j][z] += dp[i2][j][z-1]
//竖切
dp[i][j1][z] += dp[i][j2][z-1]
也就是如果是横切的话,我在 i1,j 的位置可以切 z 刀的方案数就等于原本就可以切 z 刀的方案数再加上我一刀切在 i2 ,j 位置上,然后加上 i2,j 这个位置可以切 z - 1 刀的方案数。竖切也是同理。
并且我们刚刚说过了,披萨的右下角是保持不变的,所以我们应该从披萨的右下角开始递推,而刀数是从1开始的,所以刀数从小到大遍历。
最终填完dp数组之后,根据dp数组的含义,我们返回dp[ 0 , 0 , k-1 ] ,意思就是在披萨[ 0 , 0 ]的位置,我们可以切k-1刀的数目,也就是题目要我们返回的答案。
初始化的话我们依次对披萨的每个位置进行判断,如果对应的位置的右下角有苹果的话,那么一刀不切也是可以算一种方案的,也就是
dp[i][j][0] = 1
最后要注意的就是由于答案会很大,因此每次递推我们都最结果进去取余处理。
代码:
class Solution {
public:int ways(vector<string>& pizza, int k) {int m = pizza.size(),n = pizza[0].size();vector<vector<int>>apple(m,vector<int>(n,0)); // i,j表示坐标为i,j的右下方的苹果数量for (int i = m-1; i >= 0; --i){for (int j = n-1; j >= 0; --j){if (pizza[i][j] == 'A') apple[i][j]=1;if (i == m-1 && j == n-1) continue; //防止越界提前退出.else if (j == n-1) apple[i][j] += apple[i+1][j]; //防止y轴越界else if (i == m-1) apple[i][j] += apple[i][j+1]; //防止x轴越界// 需要加上两部分并且删除重复计算的部分else apple[i][j] += apple[i+1][j] + apple[i][j+1] - apple[i+1][j+1];}}//dp[i,j,k]的含义是披萨仅剩从坐标i,j开始的右下角部分,并且可以切k刀的方案数vector<vector<vector<int>>>dp(m,vector<vector<int>>(n,vector<int>(k,0)));for (int i = m-1; i >= 0; --i){for (int j = n-1; j >= 0; --j){ if (apple[i][j] > 0) dp[i][j][0] = 1; //有苹果的话不切也是一种办法for (int z = 1; z < k; ++z){for (int y = i+1; y <= m-1; ++y){ //横切 if (apple[i][j] - apple[y][j] > 0) { //切出去上面的披萨的至少有一个苹果dp[i][j][z] = (dp[i][j][z] + dp[y][j][z-1])%1000000007;}} for (int x = j+1; x <= n-1; ++x){ //竖切if (apple[i][j] - apple[i][x] > 0){ //切出去左边的披萨至少有一个苹果dp[i][j][z] = (dp[i][j][z] + dp[i][x][z-1])%1000000007;}}}}}return dp[0][0][k-1] % 1000000007;}
};
相关文章:
【力扣每日一题】2023.8.17 切披萨的方案数
目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 题目给我们一个二维数组来表示一个披萨,其中‘A’表示披萨上的苹果。 让我们切k-1刀,把披萨切成 k 份࿰…...
Linux调试器-gdb使用
1. 背景 程序的发布方式有两种, debug 模式和 release 模式 Linux gcc/g 出来的二进制程序,默认是 release 模式 要使用 gdb 调试,必须在源代码生成二进制程序的时候 , 加上 - g 选项 2. 开始使用 gdb binFile 退出: ct…...
linux安装mysql错误处理
linux下mysql的安装与使用 linux安装mysql可有三种方式: 1、yum安装 2、源码安装 3、glibc安装 安装wget yum install -y wget https://blog.csdn.net/darendu/article/details/89874564?utm_sourceapp Linux上error while loading shared libraries问题解决方法…...
Matlab绘制灰度直方图
直方图是根据灰图像绘制的,而不是彩色图像通。查看图像直方图时候,需要先确定图片是否为灰度图,使用MATLAB2019查看图片是否是灰度图片,在读取图片后在MATLAB界面的工作区会显示读取的图像矩阵,如果是,那么…...
http学习笔记1
图解HTTP学习笔记 1.2 HTTP的诞生 CERN(欧洲核子研究组织)的蒂姆 • 伯纳斯 - 李(Tim BernersLee)博士提出了一种能让远隔两地的研究者们共享知识的设想。最初设想的基本理念是:借助多文档之间相互关联形成的超文本&am…...
PDF文件分割合并
PDF文件的分割和合并代码。 from PyPDF2 import PdfFileReader,PdfFileWriterdef pdf_split(filename,outputname)pr PdfFileReader(filename)for page in range(p.getNumPages()):pw PdfFileWriter()pw.addPage(pr.getPage(page))with open(f{outputname}{page}.pdf,wb) as…...
物联网无线通信方式总结
本文主要内容(一些物联网无线通信方式) 本文将介绍一些物联网无线通信方式的技术特点、底层调制方式和主要应用场景物联网无线通信方式是指利用无线技术实现物体之间的信息交换和网络连接的方式物联网无线通信方式的选择需要考虑多种因素,如传输距离、功耗、数据速…...
计算机竞赛 python的搜索引擎系统设计与实现
0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 python的搜索引擎系统设计与实现 🥇学长这里给一个题目综合评分(每项满分5分) 难度系数:3分工作量:5分创新点:3分 该项目较为新颖ÿ…...
ue5 场景搭建和灯光照明参考
https://www.youtube.com/watch?vOCgn40aWVuU https://www.youtube.com/watch?vIGLujClhL5U...
Mycat跨分片Join指南
前言Mycat目前版本支持跨分片的join,主要实现的方式有四种。 全局表 ER分片 HBT ShareJoin ShareJoin在开发版中支持,前面三种方式1.3.0.1支持 2.ShareJoin ShareJoin是一个简单的跨分片Join,基于HBT的方式实现。 目前支持2个表的join,原理就是解析SQL语句,拆分成单表的…...
网络:RIP协议
1. RIP协议原理介绍 RIP是一种比较简单的内部网关协议(IGP协议),RIP基于距离矢量的贝尔曼-福特算法(Bellman - Ford)来计算到达目的网络的最佳路径。最初的RIP协议开发时间较早,所以在带宽、配置和管理方面的要求也较低。 路由器运…...
如何优化因为高亮造成的大文本(大字段)检索缓慢问题
首先还是说一下背景,工作中用到了 elasticsearch 的检索以及高亮展示,但是索引中的content字段是读取的大文本内容,所以后果就是索引的单个字段很大,造成单独检索请求的时候速度还可以,但是加入高亮之后检索请求的耗时…...
HTML <table> 标签
实例 一个简单的 HTML 表格,包含两行两列: <table border="1"><tr><th>Month</th><th>Savings</th></tr><tr><td>January</td><td>$100</td></tr> </table>定义和用法 &l…...
ubuntu pdf阅读器okular
sudo apt-get install okular安装完毕后,使用如下命令浏览pdf文档 okular xxx.pdf...
根据源码,模拟实现 RabbitMQ - 虚拟主机 + Consume设计 (7)
目录 一、虚拟主机 Consume设计 1.1、承接问题 1.2、具体实现 1.2.1、消费者订阅消息实现思路 1.2.2、消费者描述自己执行任务方式实现思路 1.2.3、消息推送给消费者实现思路 1.2.4、消息确认 一、虚拟主机 Consume设计 1.1、承接问题 前面已经实现了虚拟主机大部分功…...
docker中bridge、host、container、none四种网络模式简介
目录 一.bridge模式 1.简介 2.演示 (1)运行两个容器,不指定网络模式情况下默认是bridge模式 (2)在主机中自动生成了两个veth设备 (3)查看两个容器的IP地址 (4)可以…...
排序算法之详解冒泡排序
引入 冒泡排序顾名思义,就是像冒泡一样,泡泡在水里慢慢升上来,由小变大。虽然冒泡排序和冒泡并不完全一样,但却可以帮助我们理解冒泡排序。 思路 一组无序的数组,要求我们从小到大排列 我们可以先将最大的元素放在数组…...
el-upload组件调用后端接口上传文件实践
要点说明: 使用:http-request覆盖默认的上传行为,可以添加除文件外的其他参数,注意此时仍需保留action属性,action可以传个空串给http-request属性绑定的函数,函数入参必须为param调用接口请求,注意 heade…...
深度学习-实验1
一、Pytorch基本操作考察(平台课专业课) 使用𝐓𝐞𝐧𝐬𝐨𝐫初始化一个 𝟏𝟑的矩阵 𝑴和一个 𝟐𝟏的矩阵 𝑵&am…...
互联网医院开发|医院叫号系统提升就医效率
在这个数字化时代,互联网医院不仅改变了我们的生活方式,也深刻影响着医疗行业。医院叫号系统应运而生,它能够有效解决患者管理和服务方面的难题。不再浪费大量时间在排队上,避免患者错过重要信息。同时,医护工作效率得…...
手写 Mybatis-plus 基础架构(工厂模式+ Jdk 动态代理统一生成代理 Mapper)
这里写目录标题 前言温馨提示手把手带你解析 MapperScan 源码手把手带你解析 MapperScan 源码细节剖析工厂模式Jdk 代理手撕脚手架,复刻 BeanDefinitionRegistryPostProcessor手撕 FactoryBean代理 Mapper 在 Spring 源码中的生成流程手撕 MapperProxyFactory手撕增…...
【C++11算法】iota算法
文章目录 前言一、iota函数1.1 iota是什么?1.2 函数原型1.3 参数和返回值1.4 示例代码1.5 示例代码21.6 示例代码3 总结 前言 C标准库提供了丰富的算法,其中之一就是iota算法。iota算法用于填充一个区间,以递增的方式给每个元素赋予一个值。…...
付费加密音乐格式转换Mp3、Flac工具
一、工具介绍 这是一款免费的将付费加密音乐等多种格式转换Mp3 Flac工具,现在大部分云音乐公司,比如QQ音乐、酷我音乐、酷狗音乐、网易云音乐、虾米音乐(RIP🙏)等,都推出了自己专属的云音乐格式,这些格式一般只能在制定的播放器里播放,其它的播放软件并不支持,在很多情…...
React前端开发架构:构建现代响应式用户界面
在当今的Web应用开发中,React已经成为最受欢迎的前端框架之一。它的出色性能、灵活性和组件化开发模式,使得它成为构建现代响应式用户界面的理想选择。在这篇文章中,我们将探讨React前端开发架构的核心概念和最佳实践,以帮助您构建…...
Azure Bastion的简单使用
什么是Azure Bastion Azure Bastion 是一个提供安全远程连接到 Azure 虚拟机(VM)的服务。传统上,访问 VM 需要使用公共 IP 或者设立 VPN 连接,这可能存在一些安全风险。Azure Bastion 提供了一种更安全的方式,它是一个…...
深入理解高并发编程 - 深度解析ScheduledThreadPoolExecutor
ScheduledThreadPoolExecutor 继承自 ThreadPoolExecutor 并实现了 ScheduledExecutorService 接口,这使得它可以同时充当线程池和定时任务调度器。 构造方法 public ScheduledThreadPoolExecutor(int corePoolSize) {super(corePoolSize, Integer.MAX_VALUE, 0, …...
Android---- 一个完整的小项目(消防app)
前言: 针对不同群体的需求,想着应该拓展写方向。医疗app很受大家喜欢,就打算顺手写个消防app,里面基础框架还是挺简洁 规整的。登陆注册和本地数据库写的便于大家理解。是广大学子的毕设首选啊! 此app主要为了传递 消防…...
XXX程序 详细说明
用于记录理解PC程序的程序逻辑 1、程序的作用 根据原作者的说明(文件说明.txt),该程序 (PC.py) 的主要作用是提取某一个文件夹中的某个设备 (通过config中的信息看出来是Ag_T_8) 产生的日志文件,然后提取其中某些需要的数据&…...
perl下载与安装教程【工具使用】
Perl是一个高阶程式语言,由 Larry Wall和其他许多人所写,融合了许多语言的特性。它主要是由无所不在的 C语言,其次由 sed、awk,UNIX shell 和至少十数种其他的工具和语言所演化而来。Perl对 process、档案,和文字有很强…...
Chrome谷歌浏览器修改输入框自动填充样式
Chrome谷歌浏览器修改输入框自动填充样式 背景字体 背景 input:-webkit-autofill{-webkit-box-shadow:0 0 0 1000px #fff inset !important; }字体 input:-internal-autofill-selected {-webkit-text-fill-color: #000 !important; }...
Azure CLI 进行磁盘加密
什么是磁盘加密 磁盘加密是指在Azure中对虚拟机的磁盘进行加密保护的一种机制。它使用Azure Key Vault来保护磁盘上的数据,以防止未经授权的访问和数据泄露。使用磁盘加密,可以保护磁盘上的数据以满足安全和合规性要求。 参考文档:https://l…...
Java“牵手”根据关键词搜索(分类搜索)速卖通商品列表页面数据获取方法,速卖通API实现批量商品数据抓取示例
速卖通商城是一个网上购物平台,售卖各类商品,包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取速卖通商品列表和商品详情页面数据,您可以通过开放平台的接口或者直接访问速卖通商城的网页来获取商品详情信息。以下是两种常用方法的介…...
商城-学习整理-高级-消息队列(十七)
目录 一、RabbitMQ简介(消息中间件)1、RabbitMQ简介:2、核心概念1、Message2、Publisher3、Exchange4、Queue5、Binding6、Connection7、Channel8、Consumer9、Virtual Host10、Broker 二、一些概念1、异步处理2、应用解耦3、流量控制5、概述 三、Docker安装RabbitM…...
Android Camere开发入门(1):初识Camera
Android Camere开发入门(1):初识Camera 初步了解 在Android开发中,相机(Camera)是一个常见而重要的功能模块。它允许我们通过设备的摄像头捕捉照片和录制视频,为我们的应用程序增加图像处理和视觉交互的能力。 随着Android系统的不断发展和更新,相机功能也不断改进和增…...
hive表的全关联full join用法
背景:实际开发中需要用到全关联的用法,之前没遇到过,现在记录一下。需求是找到两张表的并集。 全关联的解释如下; 下面建两张表进行测试 test_a表的数据如下 test_b表的数据如下; 写第一个full join 的SQL进行查询…...
PMP串讲
!5种冲突解决策略 !敏捷3355。 ?PMP项目管理132种工具技术合集: 参考2:项目管理的132种工具 - 水之座 ?质量管理,有多少种图: ?风险管理,有多少种图: --参考:PMP相关的十八种…...
最长回文子序列——力扣516
动态规划 int longestPalindromeSubseq(string s){int n=s.length();vector<vector<int>>...
从零实现深度学习框架——Transformer从菜鸟到高手(二)
引言 💡本文为🔗[从零实现深度学习框架]系列文章内部限免文章,更多限免文章见 🔗专栏目录。 本着“凡我不能创造的,我就不能理解”的思想,系列文章会基于纯Python和NumPy从零创建自己的类PyTorch深度学习框…...
docker监控平台FAST OS DOCKER --1
感觉这个是目前好用的中文平台,暂为v1吧 拉取镜像 docker pull wangbinxingkong/fast运行镜像 docker run --name fastos --restart always -p 18091:8081 -p 18092:8082 -e TZ"Asia/Shanghai" -d -v /var/run/docker.sock:/var/run/docker.sock -v /e…...
SpringBoot2.0集成WebSocket
<!-- websocket --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId></dependency> 新建配置类 import org.springframework.boot.autoconfigure.condition.Cond…...
Vue的Ajax请求-axios、前后端分离练习
Vue的Ajax请求 axios简介 Axios,是Web数据交互方式,是一个基于promise [5]的网络请求库,作用于node.js和浏览器中,它是 isomorphic 的(即同一套代码可以运行在浏览器和node.js中)。在服务端它使用原生node.js http模块, 而在…...
Spring源码深度解析三 (MVC)
书接上回 10.MVC 流程&源码剖析 * 问题1:Spring和SpringMVC整合使用时,会创建一个容器还是两个容器(父子容器?) * 问题2:DispatcherServlet初始化过程中做了什么? * 问题3:请求…...
API接口漏洞利用及防御
API是不同软件系统之间进行数据交互和通信的一种方式。API接口漏洞指的是在API的设计、开发或实现过程中存在的安全漏洞,可能导致恶意攻击者利用这些漏洞来获取未授权的访问、篡改数据、拒绝服务等恶意行为。 1.API接口漏洞简介 API(Application Progr…...
解决Spring mvc + JDK17@Resource无法使用的情况
问题描述 我在使用jdk17进行Spring mvc开发时发现 Resource用不了了。 原因 因为JDK版本升级的改动,在Jdk9~17环境下,搭建Springboot项目,会出现原有Resource(javax.annotation.Resource)不存在的问题,导…...
页面禁用鼠标右键,禁用F12打开开发者工具!!!
文章目录 问题分析方法一方法二方法二问题 今天在浏览博主文章时发现无法复制页面上的内容,也无法F12打开开发者工具,更用不了鼠标右键,于是上网找了原因并亲测可用 分析 方法一 将 <body> 改成 <body oncontextmenu=self.event.returnValue=false>方法二 …...
Android中使用JT808协议进行车载终端通信的实现和优化
JT808是一种在中国广泛应用的车载终端通信协议,用于车辆与监控中心之间的数据通信。下面是关于Android平台上使用JT808协议进行通信的一般步骤和注意事项: 协议了解:首先,您需要详细了解JT808协议的规范和定义。该协议包含了通信消…...
导出pdf
该方法导出的pdf大小是A4纸的尺寸,如果大于1页需要根据元素高度进行截断的话,页面元素需要加 class ergodic-dom,方法里面会获取ergodic-dom元素,对元素高度和A4高度做比较,如果大于A4高度,会塞一个空白元素…...
【考研数学】线形代数第三章——向量 | 基本概念、向量组的相关性与线性表示
文章目录 引言一、向量的概念与运算1.1 基本概念1.2 向量运算的性质 二、向量组的相关性与线性表示2.1 理论背景2.2 相关性与线性表示基本概念2.3 向量组相关性与线性表示的性质 引言 向量是线性代数的重点和难点。向量是矩阵,同时矩阵又是由向量构成的,…...
温故知新之:接口和抽象类有什么区别?
本文以下内容基于 JDK 8 版本。 1、接口介绍 接口是 Java 语言中的一个抽象类型,用于定义对象的公共行为。它的创建关键字是 interface,在接口的实现中可以定义方法和常量,其普通方法是不能有具体的代码实现的,而在 JDK 8 之后&…...
回归预测 | MATLAB实现SSA-RF麻雀搜索优化算法优化随机森林算法多输入单输出回归预测(多指标,多图)
回归预测 | MATLAB实现SSA-RF麻雀搜索优化算法优化随机森林算法多输入单输出回归预测(多指标,多图) 目录 回归预测 | MATLAB实现SSA-RF麻雀搜索优化算法优化随机森林算法多输入单输出回归预测(多指标,多图)…...