作者：韩信子@ShowMeAI，章鱼@高德专栏：计算机视觉 http://www.showmeai.tech/tutorials/51 地址：http://www.showmeai.tech/article-detail/93声明：版权所有，转载请联系平台与作者并注明出处收藏 ShowMeAI 查看更多精彩内容一图看懂全文获取『计算机视觉』行业解决方案公众号 ShowMeAI研究中心 回复关键字『计算机视觉』，获取 ShowMeAI 整理的 大厂解决方案 —— 包含腾讯、爱奇艺、美团、小米、百度、淘宝、高德等项目代码、数据集、论文合辑等打包资料。相关代码实现参考ShowMeAI社区的技术专家小伙伴们也对图像检索的典型算法做了实现，构建了相关应用。对『基于CNN与三元组的图像检索实现』细节感兴趣的话，请前往我们的 GitHub项目 https://github.com/ShowMeAI-Hub/image_retrieval 查看实现代码。感谢 AI算法研究所 参与此项目的所有技术专家小伙伴，推荐大家关注公众号。数据集和代码的整理花费了很多心思，欢迎大家 PR 和 Star！一、高德图像检索的业务背景本文应用到的技术是图像检索，应用场景为高德地图，应用点是高德地图的 POI信息更新（在高德图像数据中，POI牌匾和POI一一对应）。POI：Point of Interest，在电子地图上，POI 代表餐厅、超市、政府机关、旅游景点、交通设施等。POI是电子地图的核心数据。POI 数据包含的名称信息、位置信息等，能满足用户的基本需求——使用电子地图“查找目的地”，进而唤起导航服务。POI 数据可以支持电子地图提供“搜索附近”、“点评”等功能，这些操作可以提高用户的使用和活跃时长。POI 数据还是线上线下连接互动的一个纽带，是基于位置服务（Location Based Service）产业的一个重要组件。高德地图的业务场景，需要根据自有图像源，将每个新增或调整的 POI及时制作成数据。一般来讲，短时间片（月度）内，同一地点的 POI 的变化量很低（如图，只有“汤火功夫”POI 是一个新增的挂牌）。因此，从技术实现的角度来看，不能采用『每次都处理全部 POI 』的方案，因为作业成本太高了。更好的实现方案是，将没有变化的 POI 自动化地过滤掉。这个场景任务是非常典型的图像检索任务，其中关键技术图像匹配。1.1 图像检索的任务定义图像检索问题定义：给定查询图像（Query），通过分析视觉内容，在大型图像库中（Gallery）中搜索出相似的图像。图像检索一直是计算机视觉领域的一个长期研究课题，在『行人重识别』、『人脸识别』、『视觉定位』等任务中均有广泛的应用。图像检索的过程需要『图像特征抽取』+『比对检索』两个环节：1）图像特征提取通常包括：全局特征、局部特征、辅助特征等，主要是针对不同任务特点进行相应的优化。例如：行人重识别以及人脸识别具有很强的刚性约束，并且具备明显的关键特征（行人/人脸关键点），因此会将人体分割或关键点检测信息融合到模型特征提取中。2）比对检索核心技术是度量学习，其目标是在固定维度的特征空间中，约束模型将同类别样本拉近，不同类别样本推远。在深度学习时代，主要有几种经典的结构，均是通过正负样本定义以及损失函数设计上进行优化：对比损失（Contractive Loss）三元组损失（Triplet Loss）中心损失（Center Loss）1.2 高德业务问题与难点POI 牌匾的图像检索和学术上主流检索任务（如行人重识别）有着较大的区别，主要包括以下几点：异质数据遮挡影响文本依赖性1）异质数据异质数据指的是不同相机拍摄、不同环境、不同条件下的图像差异。比如，在 POI 牌匾检索场景中，有比较严重的异质数据问题。如下图所示，是不同拍摄条件下的异源图像。由于拍摄相机的品质、拍摄视角的不同，POI 牌匾最终的亮度、形状、清晰度等都存在非常大的差异。如何在差异较大的异质数据中实现 POI 牌匾检索，则是一个非常具有挑战性的问题。2）遮挡影响在道路场景中，经常存在树木以及车辆等干扰信息，并且由于拍摄视角原因，拍摄到的 POI 牌匾经常会面临严重的遮挡问题。遮挡给 POI 牌匾检索带来巨大的挑战。3）文本依赖性POI 牌匾还有一个独有特性就是对文本强依赖，主要是对 POI 名称文本的依赖。在该场景下，希望两个牌匾不要匹配。这就需要引入文本特征来增强特征区分性。遮挡问题也同样会影响文本特征的有效表达，因此需要结合图像特征进行权衡。但是文本特征和图像特征来自多个模态，如何将多模信息进行融合也是该业务特有的技术难点。二、技术实现总体方案牌匾检索的技术方案主要包括『数据生成』和『模型优化』两块。整体技术框架如下图所示：2.1 数据生成模块『数据生成』模块，分为了『冷启动自动生成数据』以及『模型迭代生成数据』两个步骤：【1】利用传统匹配算法 Sift 自动生成模型所需的训练数据，完成模型的冷启动；【2】模型上线后，对线上人工作业结果进行自动挖掘，并组织成训练数据，以迭代模型优化。2.2 模型优化模块『模型优化』模块，考虑到牌匾的文本信息比较丰富，因此将视觉信息与文本信息进行融合，高德团队基于三元组损失（Triplet Los）的度量学习框架下设计了一个『多模态检索模型』：设计了『视觉分支』和『文本分支』两部分。『视觉分支』的输入是 POI 牌匾的图像信息，使用双分支进行特征提取；『文本分支』的输入是 POI 牌匾的文本信息，使用BERT进行特征提取。针对视觉信息特征的提取，进一步设计了『全局特征分支』与『局部特征』分支，并分别进行了优化。三、数据生成模块为训练检索模型，通常需要进行实例级标注，即按照 POI 牌匾粒度进行标注。但是在不同资料中筛选同一 POI 牌匾是一件非常复杂的工作，如果进行人工标注的话，则会带来高昂的标注成本，并且无法大规模标注。因此，高德设计了一套简单高效的训练数据自动生成方式，用于模型冷启动，整个环节无需任何人工标注。具体过程为：借鉴传统特征点匹配算法思想，利用 Sift特征点匹配算法 对两趟资料中的所有牌匾进行两两匹配，并通过内点数量对匹配结果进行筛选，即内点数量大于阈值的匹配牌匾视作同一牌匾。3.1 传统特征点匹配算法存在的问题传统特征点匹配算法会存在泛化性不足问题，由此生成的训练数据很可能导致模型无法很好学习，具体体现在：【1】训练样本较为简单。【2】类别冲突，即同一牌匾分为多个类别。【3】类别错误，即不同牌匾分为同一类别。3.2 高德团队的优化方式【1】采用『多趟资料』匹配结果，提升同一类别下牌匾的多样性；高德使用了『多趟资料』的匹配结果来生成训练数据。因为在不同资料中，同一牌匾存在多张来自不同视角的拍摄结果，这就保证了同一类别下牌匾的多样性，避免了自动生成的样本都为简单样本问题。【2】采用『Batch 采样策略』以及『MDR Loss』，来降低模型对错误标签数据的敏感性。Batch采样策略，即按类别进行采样，而数据中类别总数远远大于 Batch Size，因此可以缓解类别冲突的问题。MDR Loss 是在 Triplet Loss 基础上设计了根据不同距离区间进行正则化约束的新的度量学习框架，从而减少模型对对噪声样本的过拟合。下图是 Triplet Loss 和 MDR Loss 的对比示意图。 MDR Loss 距离正则约束，希望正样本（Positive）和 基准样本（Anchor）之间的距离不被拉到无限近，同时负样本（Negative）也不希望被推到无限远。以类别错误噪声样本来说，不同牌匾被误分为同一类别，按照 Triplet Loss 的优化目标则会强制模型将两者距离学习到无限近。这样的话，模型会过拟合到噪声样本上，从而导致最终效果较差。四、模型优化模块为了优化牌匾检索效果，高德的解决方案设计了多模态检索模型，对牌匾中的视觉信息与文本信息进行了融合。针对视觉信息，优化模型全局（Global）特征和局部（Local）特征的提取能力。针对文本信息，使用BERT对牌匾的 OCR 结果进行编码，将其作为辅助特征，并与视觉特征融合后进行度量学习。4.1 全局特征通常对于检索任务来说，使用深度学习模型提取到的全局特征具有更高的鲁棒性，可以适应牌匾视角、颜色、光照变化等不同场景。为了进一步提升全局特征的鲁棒性，高德的解决方案主要从以下两方面进行了优化：采用『注意力（Attention）机制』，加强对重要特征的关注。网络 Backbone 的改进，以关注到更多细粒度特征。1）引入注意力机制在高德实际业务场景中，存在一些外观相似而细节有一定差异的牌匾，在这种情况下，希望模型可以关注到牌匾中的细粒度信息，比如『牌匾中文字的字体』、『文字排版』或者是『文字内容』本身。注意力机制，可以帮助模型在大量信息中准确地关注到能够区分不同牌匾更为关键的部分。因此，合理的想法是在网络中引入了注意力模块，让模型学习关键信息，以提升全局特征的辨别能力。高德团队采用了『空间注意力机制（Spatial Group-wise Enhance，SGE）』。SGE 通过对特征图上的每个空间位置生成一个注意力因子，来调整每个空间位置处特征的重要性。SGE 模块如图所示：首先对特征图进行分组。对每组特征图计算语义特征向量。使用语义特征向量和特征图进行 position-wise 点乘，得到注意力图。将注意力图与特征图进行 position-wise 点乘，以此来增强特征，从而获得在空间上分布更好的语义特征。2）改进网络 Backbone为了减少局部特征的损失，可以对网络 Backbone 进行改进：取消 ResNet 网络最后一个 block 中的下采样，使得最终的特征图中包含更多的局部信息。使用 GeM 池化层替代最后一个 Global Average Pooling：GeM是一种可学习的特征聚合方法，Global Max Pooling 和 Global Average Pooling 都是它的特殊情况，使用GeM池化可以进一步提升全局特征鲁棒性。4.2 局部特征在针对全局特征进行优化以后，现有模型仍然在以下三个方面表现不够好：截断的牌匾，特征学习质量差，如上图 (a)。遮挡的牌匾，特征中引入一些无关的上下文信息，如上图 (b)。相似但不同的牌匾，难以区分，如上图 ( c)。针对以上3点，高德的解决方案进一步设计了局部特征分支，让模型更加关注牌匾的『几何』、『纹理』等『局部信息』，与『全局特征』共同做牌匾检索。针对『局部特征』的提取，主要思路是将牌匾垂直切分成几个部分，分别关注每个部分的局部特征，并对局部特征进行对齐后优化。对齐操作如上图所示：将特征图进行垂直池化，得到分块的局部特征图。计算两张图局部特征之间的相似度矩阵，然后根据公式1找到最短距离将两张图像进行对齐。， 分别表示两张图中的第i块特征和第j块特征。 表示两张图中第 块和第 块特征的欧式距离。通过这种方式进行局部特征对齐，可以很好地提升牌匾在截断、遮挡、检测框不准等情况下的检索效果。4.3 文本特征POI 牌匾对文本强依赖，可能存在『仅牌匾名称文本发生变化』的场景。在上述设计的全局特征分支以及局部特征分支，可一定程度上学习到文本特征，但是文本信息在整体信息中占比较小，并且监督信号仅为两张图是否相似，导致文本特征并没有被很好的学习到。解决的方法是，利用已有的文本 OCR 识别结果，引入 BERT 对 OCR 结果进行编码得到文本特征，作为辅助特征分支和视觉特征进行融合，融合后的特征用于最终的牌匾检索度量学习。解决方案中的一个细节点：在对牌匾提取 OCR 结果时，为了减少单帧内识别结果不准的影响，利用了一趟资料内同一牌匾的多帧 OCR 结果，并且将所得到的 OCR 结果进行拼接，使用 BERT 对 OCR 结果特征编码时，对来自不同帧的 OCR 结果之间插入 SEP 符号做区分。五、业务效果在新的技术方案下，高德 POI 牌匾图像检索取得了非常好的效果。准确率和召回率都大于95%，大幅提升了线上指标，并且模型速度也有了巨大的提升。在优化过程中，有一些非常难的 Case 也在逐渐被解决，如图所示。(a)、(b)、(c)展示的是此方案之前的 Bad Case（左图为 query 图像，右图为 Rank1 检索结果）。从 Bad Case 中不难发现，牌匾检索对细粒度特征提取要求非常高，因为这些 Case 普遍特点是具备整体相似性，但是局部特征有区别。这些 Bad Case 也是设计多模态检索模型的初衷，并且也在优化过程逐渐得以解决，如图(d)、(e)、(f)所示。多模态检索模型通过对全局特征优化以及引入局部特征对齐，使得模型更多关注到牌匾上更有区分性的局部特征，如文字信息，文字字体、板式，牌匾纹理等，因此模型对于外观相似的不同牌匾具有更好的区分能力，如图(a) 和图(d)效果对比。此外，由于不同视角牌匾存在遮挡、拍摄时的光照强度不同以及不同相机色彩差异大等因素，部分牌匾只利用视觉特征检索非常困难。因此，通过辅助特征分支加入了 OCR 信息，进一步增强了特征的鲁棒性，使得牌匾检索可以综合考虑牌匾的视觉信息和牌匾中的文本信息进行检索，如图(b) 和图(e)效果对比。六、总结与下一步优化方向上述图像检索方案在高德实际业务中应用，帮助完成一定的数据自动化生产。但是模型并不是完美的，仍会存在 Bad Case，可以考虑：半监督学习/主动学习自动补充数据。引入 Transformer 结构。6.1 半监督学习/主动学习数据挖掘数据是非常重要的，模型本身是数据驱动的，补充数据对于模型有非常大的帮助，针对性补充数据能帮助模型处理极端的 Case。补充数据的关键是如何挖掘 Corner Case 并自动针对性标注，半监督学习以及主动学习是比较有前景的方法。1）半监督学习利用有标签数据训练出的模型来对海量无标签数据产生伪标签，进一步标签数据和伪标签数据混合后再优化模型。半监督学习是完全由模型自身产生标签，但是可能导致模型效果存在上限。2）主动学习利用有标签数据训练出的模型对海量无标签数据进行数据挖掘，并人工标注挖掘出的有价值数据。主动学习则可以一定程度提高半监督学习能达到的上限。有效地结合两者，可以更好地补充训练数据，解决 Corner Case。6.2 Transformer特征提取与融合Transformer 是近年来非常有效的模型结构，在 NLP 领域早就大放异彩，大部分预训练模型都采用了它的结构和设计思路。其在计算机视觉领域大量场景任务（分类、检测、分割、跟踪以及行人重识别）上也有优异的表现。Transformer 相比于 CNN，具有全局感受野，并且能进行高阶相关性建模，在很多任务的特征提取上有着更好的表征能力。Transformer 的输入也很灵活，可以方便地将其他模态信息进行编码，并和图像特征一起输入到模型中，因此其在多模特征融合上也有较大的优势。一个优化方向是，通过 Transformer 对图像 Patch 的相关性建模来解决 POI 牌匾在遮挡/截断场景下的匹配效果，并通过对文本特征编码来实现多模特征的融合。七、代码实现参考获取『计算机视觉』行业解决方案公众号 ShowMeAI研究中心 回复关键字『计算机视觉』，获取 ShowMeAI 整理的 大厂解决方案 —— 包含腾讯、爱奇艺、美团、小米、百度、淘宝、高德等项目代码、数据集、论文合辑等打包资料。相关代码实现参考ShowMeAI社区的技术专家小伙伴们也对图像检索的典型算法做了实现，构建了相关应用。对『基于CNN与三元组的图像检索实现』细节感兴趣的话，请前往我们的 GitHub项目 https://github.com/ShowMeAI-Hub/image_retrieval 查看实现代码。感谢 AI算法研究所 参与此项目的所有技术专家小伙伴，推荐大家关注公众号。数据集和代码的整理花费了很多心思，欢迎大家 PR 和 Star！八、参考文献[1] Zhang X, Luo H, Fan X, et al. Alignedreid: Surpassing human-level performance in person re-identification[J]. arXiv preprint arXiv:1711.08184, 2017.[2] Kim, Yonghyun, and Wonpyo Park. "Multi-level Distance Regularization for Deep Metric Learning." arXiv preprint arXiv:2102.04223，2021.[3] Radenović F, Tolias G, Chum O. Fine-tuning CNN image retrieval with no human annotation[J]. IEEE transactions on pattern analysis and machine intelligence, 2018, 41(7): 1655-1668.[4] Li X, Hu X, Yang J. Spatial group-wise enhance: Improving semantic feature learning in convolutional networks[J]. arXiv preprint arXiv:1905.09646, 2019.ShowMeAI 大厂技术实现解决方案推荐『推荐与广告计算』大厂解决方案大厂技术实现 | 多目标优化及应用（含代码实现）@推荐与广告计算系列大厂技术实现 | 爱奇艺短视频推荐业务中的多目标优化实践@推荐与计算广告系列大厂技术实现 | 腾讯信息流推荐排序中的并联双塔CTR结构@推荐与计算广告系列『计算机视觉』大厂解决方案大厂技术实现 | 图像检索及其在淘宝的应用@计算机视觉系列大厂技术实现 | 图像检索及其在高德的应用@计算机视觉系列『自然语言处理』大厂解决方案大厂技术实现 | 详解知识图谱的构建全流程@自然语言处理系列大厂技术实现 | 爱奇艺文娱知识图谱的构建与应用实践@自然语言处理系列ShowMeAI系列教程精选推荐图解Python编程：从入门到精通系列教程图解数据分析：从入门到精通系列教程图解AI数学基础：从入门到精通系列教程图解机器学习算法：从入门到精通系列教程机器学习实战：手把手教你玩转机器学习系列深度学习教程：吴恩达专项课程 · 全套笔记解读自然语言处理教程：斯坦福CS224n课程 · 课程带学与全套笔记解读深度学习与计算机视觉教程：斯坦福CS231n · 全套笔记解读

0x00 教程内容Spark GraphX 理论GraphX 重要概念与实操0x01 Spark GraphX 介绍1. GraphX 介绍GraphX 是 Spark 四大核心组件之一，它也是使用 Spark 作为计算引擎的，GraphX 是用于图形和图形并行计算的组件，实现了大规模图计算的功能。GraphX 的出现使 Spark 生态系统变得更加完善和丰富，同时它能够与 Spark 生态系统的其它组件天然融合，再加上它强大的图数据处理能力，在工业届得到了广泛的运用。在高层次上，GraphX 通过引入一个新的图形抽象来扩展 Spark RDD ：即顶点和边带有特性的有向多重图。GraphX 提供了一些基本运算符以及优化了的 Pregel API。 此外，GraphX 提供了大量的图算法和构建器，以简化图形分析任务。GraphX 有两个RDD， 一个是点RDD，一个是边RDD。Vertex：表示顶点，每个顶点都会有一个唯一标识以及这个顶点的属性 。Edge：表示有向边，由一个源顶点id，一个目标顶点id以及这条边的属性组成 。这些关系，都可以转化为相应的表来描述。2. GraphX 的使用场景在社交网络中，比如：Twitter、Facebook、微博、微信等，人与人之间存在着很多的关系链。这些地方产生的数据更加适合使用图处理来进行计算。图的分布式或者并行处理其实是把图拆分成很多个子图，然后分别对这些子图进行计算，计算的时候可以分别迭代进行分阶段的计算，即对图进行并行计算。0x02 GraphX 重要概念与实操1. 属性图属性图是一个有向多重图，它的每个顶点和每条边都附有用户定义的对象。作为有向图，有向多重图可能有多个平行的边来共享相同的源顶点和目标顶点。作为多重图，它支持并行边，这个特性简化了许多涉及多重关系的建模场景。每个顶点的主键是一个长度为64 bit的唯一标识符（VertexID）。GraphX没有为顶点添加任何顺序的约束。类似地，每一条边有对应的源顶点和目标顶点的标识符。因此，属性图的参数是通过顶点（VD）和边的类型（ED）来决定的。在某些情况下，你可能希望在同一个图里面，顶点能够有不同的属性类型。这个想法可以通过继承实现。举个例子，我们可以对用户和产品进行建模，将其作为一个二分图，然后进行如下的定义：class VertexProperty() case class UserProperty(val name: String) extends VertexProperty case class ProductProperty(val name: String, val price: Double) extends VertexProperty // 图可能会有这个类型 var graph: Graph[VertexProperty, String] = null 类似于 RDD，属性图是不可变的、分布式的，并且具有容错性。对于图而言，它的值或者结构上的改变，是通过产生带有预期改变的新图来完成的。主要注意的是，原始图的主要部分（即不受影响的结构、属性和索引等）在新图中被重用，以减少固有功能的数据结构成本。通过使用大量的启发式顶点分区，图在不同的执行器里被划分。就像 RDD 一样，图的每个分区可以在发生故障时被不同的机器重建。属性图在逻辑上对应于一对类型化集合（RDD），该集合编码了每个顶点和每条边属性。因而，图类包含了可以访问图的顶点和边的成员，它的定义如下：class Graph[VD, ED] { val vertices: VertexRDD[VD] val edges: EdgeRDD[ED] } VertexRDD[VD]类和EdgeRDD[ED]类分别继承和优化了RDD[(VertexID, VD)]类和RDD[Edge[ED]]类。两者都提供基于图计算和内部优化构建的额外功能。在此你可将其简单地理解为以RDD[(VertexID, VD)]和RDD[Edge[ED]]形式定义的 RDD。2. 多种方式理解GraphXa. EdgeTriplet表示val facts: RDD[String] = graph.triplets.map(triplet => triplet.srcAttr._1 + " is the " + triplet.attr + " of " + triplet.dstAttr._1)b. SQL表示triplet表示SELECT src.id, dst.id, src.attr, e.attr, dst.attr FROM edges AS e LEFT JOIN vertices AS src, vertices AS dst ON e.srcId = src.Id AND e.dstId = dst.Idc. 图表示triplet表示3. 属性图编程示例现在假设我们要构建一个由许多来自 GraphX 项目组的协作者组成的属性图。顶点的属性可能包含用户名和职业。我们应该用一个可以描述协作者间的关系的字符串来注释图的边。依然是使用上面的图：启动Spark Shell：spark-shell编写案例代码：import org.apache.spark.graphx.{Edge, Graph, VertexId} import org.apache.spark.rdd.RDD // 如果不是在 `spark-shell` 中操作，则还需要额外引入 `SparkContext`。 // val sc: SparkContext // 创建一个RDD用于表示顶点 val users: RDD[(VertexId, (String, String))] = sc.parallelize(Array((3L, ("xiaoshao", "student")), (7L, ("laoshao", "Postdoctoral")), (5L, ("laonai", "professor")), (2L, ("laoyi", "professor")))) // 创建一个RDD用于表示边 val relationships: RDD[Edge[String]] = sc.parallelize(Array(Edge(3L, 7L, "partner"), Edge(5L, 3L, "mentor"),Edge(2L, 5L, "worker"), Edge(5L, 7L, "leader"))) // 定义默认的用户，用于建立与缺失的用户之间的关系 val defaultUser = ("spark", "default") // 构造图对象，即初始化 val graph = Graph(users, relationships, defaultUser) Edge类有srcId和dstId，分别对应于源顶点和目标顶点的标识符。另外，Edge类有一个名为attr的成员，用于存储边的属性，可以结合着表来理解。执行过程如图：我们可以进一步操作，使用graph.vertices和graph.edges函数来解构一个图，将其转化为各个顶点和边的视图，并且实现一些简单的统计操作：// 看看博士后的有多少人 graph.vertices.filter { case (id, (name, pos)) => pos == "Postdoctoral" }.count // 源顶点id大于目标顶点id的数量 graph.edges.filter(e => e.srcId > e.dstId).count// 显示关系 val facts: RDD[String] = graph.triplets.map(triplet => triplet.srcAttr._1 + " is the " + triplet.attr + " of " + triplet.dstAttr._1) facts.collect.foreach(println(_)) 解释：graph.vertices函数的返回值类型是 VertexRDD[(String, String)]，它继承了 RDD[(VertexID, (String, String))]，所以我们可以用 Scala 的 case 表达式来解构这个元组。另外，graph.edges函数的返回值类型是EdgeRDD，它包含了Edge[String]对象。0xFF 总结更多学习请参考官网：https://spark.apache.org/docs/latest/graphx-programming-guide.html推荐一本入门GraphX的入门书籍：《Spark GraphX实战》，挺适合初学者入门。

1 简介In the fifield of saliency detection, many graph-based algorithms use boundary pixels as background seeds to estimate the background and foreground saliency,which leads to signifificant errors in some of pictures. In addition, local context with high contrast will mislead the algorithms. In this paper, we propose a novel multilevel bottom-up saliency detectionapproach that accurately utilizes the boundary information and takes advantage of both region based features and local image details. To provide more accurate saliency estimations, we build a three-level graph model to capture both region-based features and local image details. Byusing superpixels of all four boundaries, we fifirst roughly fifigure out the foreground superpixels.After calculating the RGB distances between the average of foreground superpixels and every boundary superpixel, we discard the boundary superpixels with the longest distance to get a set of accurate background boundary queries. Finally, we propose the regularized random walks ranking to formulate pixel-wise saliency maps. Experiment results on two public datasets indicate the signifificantly promoted accuracy and robustness of our proposed algorithm in comparison with7 state-of-the-art saliency detection approaches.2 部分代码clear allclcclose all%% Initializationaddpath(genpath('./support/'));IMG_DIR = './TestData/data/';% Original image pathSAL_DIR='./TestData/solution/' ;% Output path of the saliency mapif ~exist(SAL_DIR, 'dir') mkdir(SAL_DIR);endimglist=dir([IMG_DIR '*' 'jpg']);%% Algorithm startfor imgno=1:length(imglist) % Load input image disp(imgno); disp(imglist(imgno).name); % Calculate saliency imgnamein=imglist(imgno).name; spn = 200; spnb = 24; itheta = 10; alpha = 0.99; % Step 1 & 2: Saliency Estimation imgname = [IMG_DIR, imgnamein(1:end-4) '.jpg']; imgbmpname = strcat(imgname(1:(end-4)), '.bmp'); [img, wid] = removeframe(imgname); img = uint8(img*255); w=fspecial('gaussian',[5,5],15); img2=imfilter(img,w);%%%%%%%%%%%1st gaussian w=fspecial('gaussian',[55,55],15); img3=imfilter(img,w);%%%%%%%%%%%2st gaussian [m, n, ~] = size(img); comm = ['SLIC_SUPPORT' ' ' imgbmpname ' ' int2str(2) ' ' int2str(spn) ' ']; evalc('system(comm)'); spname = [imgbmpname(1:end-4) '.dat']; superpixels = ReadDAT([m,n], spname); spno = max(superpixels(:)); [salest,W] = Msalestimation(img, superpixels, spno, itheta, alpha,img2,img3); salest= (salest-min(salest))/(max(salest)-min(salest)); map=superpixels; for i=1:spno map(map==i)=salest(i); end map1=reshape(map',n*m,1); % Step 3: regularized random walk ranking salest=salest(1:spno,1); th1 = (mean(salest) + max(salest)) / 2; th2 = mean(salest); mu = (1-alpha) / alpha; [seeds, label] = seed4rw(salest, th1, th2); [P] = myrrwr(m,n,img,itheta,superpixels,seeds,label,salest,spno,mu); sal = P(:,1); salmean = (sal+map1)/2; sal = (salmean-min(salmean(:)))/(max(salmean(:))-min(salmean(:))); sal=reshape(sal,n,m)'; saloutput = zeros(wid(1),wid(2)); saloutput(wid(3):wid(4),wid(5):wid(6)) = sal; saloutput = uint8(saloutput*255); saliency=saloutput; % Output saliency map to file imwrite(saliency, [SAL_DIR, imglist(imgno).name(1:end-4), '_Saliency.png']); salest=salest(1:spno,1); th1 = (mean(salest) + max(salest)) / 2; th2 = mean(salest); mu = (1-alpha) / alpha; [seeds, label] = seed4rw(salest, th1, th2); [~, probabilities] = rrwr(img, superpixels, salest, seeds, label, mu); sal = probabilities(:,:,1); sal = (sal-min(sal(:)))/(max(sal(:))-min(sal(:))); saloutput = zeros(wid(1),wid(2)); saloutput(wid(3):wid(4),wid(5):wid(6)) = sal; saloutput = uint8(saloutput*255); saliency=saloutput; % Output saliency map to file figure subplot(121); imshow(img); title('原图') subplot(122); imshow(saliency) ; title('显著图') imwrite(saliency, [SAL_DIR, imglist(imgno).name(1:end-4), '_SaliencyOld.png']); % imwrite(map, [SAL_DIR, imglist(imgno).name(1:end-4), '_sal锟洁级BB.png']); clearvars -except IMG_DIR SAL_DIR imglist imgnoend3 仿真结果4 参考文献[1]Hao, Aimin, Shuai, et al. Structure-Sensitive Saliency Detection via Multilevel Rank Analysis in Intrinsic Feature Space[J]. IEEE Transactions on Image Processing, 2015, 24(8):2303-2316.博主简介：擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真，相关matlab代码问题可私信交流。部分理论引用网络文献，若有侵权联系博主删除。

数据结构与算法学习——动态规划-3目录博主介绍前言1、礼物的最大价值1.2、最长不含重复字符的子字符串1.3、把数字翻译成字符串1.4、删除并获得点数1.5、接雨水1.6、丑数 II1.7、跳跃游戏 I1.8、跳跃游戏 II1.9、环形子数组的最大和2、乘积最大子数组2.1、乘积为正数的最长子数组长度背包1.1、背包回顾1.2、使用一维滚动数组优化背包问题1.3、目标和1.4、使用一维滚动数组优化分割等和子集问题1.5、最后一块石头的重量 II1.6、一和零完全背包问题1.1、完全背包问题理论说明1.2、零钱兑换1.3、零钱兑换 II1.4、组合总和 IV1.5、爬楼梯1.6、完全平方数背包问题总结1.1、根据所给条件分类1.2、根据待求项分类1.3、组合问题和排列问题编辑距离问题总结1.1、判断子序列1.2、不同的子序列1.3、两个字符串中的删除操作1.4、编辑距离💫点击直接资料领取💫目录博主介绍💂 个人社区:CSDN全国各地程序猿🤟作者介绍：中国DBA联盟(ACDU)成员，CSDN全国各地程序猿（媛）聚集地管理员。目前从事工业自动化软件开发工作。擅长C#、Java、机器视觉、底层算法等语言。2019年成立柒月软件工作室，2021年注册苏州凯捷智能科技有限公司💬如果文章对你有帮助，欢迎关注、点赞、收藏（一键三连）和C#、Halcon、python+opencv、VUE、各大公司面试等一些订阅专栏哦💅 有任何问题欢迎私信，看到会及时回复👤 微信号：stbsl6，微信公众号：苏州程序大白🎯 想加入技术交流群的可以加我好友，群里会分享学习资料前言🥝数据结构与算法学习——动态规划-1🥝🥝数据结构与算法学习——动态规划-2🥝继续数据结构与算法学习——动态规划-1、动态规划-2讲解1、礼物的最大价值1、题目描述在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？示例一输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物2、解题思路确定 dp 数组的含义其中 dp[i][j] 表示到达棋盘上的 [i , j] 位置时，所能拿到的礼物的总价值。状态转移方程对于棋盘上的某个位置 (i, j) 来说 ，它的状态可以由两个状态得来，即它的上方元素 （i - 1,j） 和左边元素 （i, j - 1） 得到，同时还需要加上当前位置礼物的价值 nums[i][j]，我们需要在上面的选择中取较大值。dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + nums[i][j];初始化 dp 数组我们需要初始化第一行和第一列的元素其中第一行的元素为 nums[0,i]上的元素累加值，比如说，在例子中， dp[0][0]应该初始化为 nums[0][0]，dp[0][1]应该初始化为 nums[0][0] + nums[0][1]，dp[0][2] = nums[0][0] + nums[0][1] + nums[0][2]。同理，第一列的元素也应该按照上面的规则初始化，只不过变为向下累加。遍历顺序这道题是最常规的动态规划问题，我们只需要按照从头到尾的顺序进行遍历即可，可以看到 dp[i][j] 是由上一行、前一列的元素推导出来的。3、解题代码 public int maxValue(int[][] grid) { if (grid == null || grid.length == 0) return 0; int row = grid.length; int column = grid[0].length; int[][] dp = new int[row][column]; int value = 0; // 初始化 dp 数组 for (int i = 0;i < row;i++) { value += grid[i][0]; dp[i][0] = value; } value = 0; for (int j = 0;j < column;j++) { value += grid[0][j]; dp[0][j] = value; } for (int i = 1;i < row;i++) { for (int j = 1;j < column;j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[row - 1][column - 1]; } 1.2、最长不含重复字符的子字符串1、题目描述请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。示例一输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例二输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。2、解题思路明确 dp 数组的含义其中 dp[i] 表示以字符 s.charAt(i) 结尾的最长不含重复字符的子字符串的长度。明确状态转移方程对于 i 位置的字符 x 来说，我们需要找到 x 在 s 中的上一个位置 index ，然后根据 index 来判断下一步该如何选择。1、如果 index == -1 ，此时代表 x 字符串在 [0, i - 1]位置内不曾出现，那么 x 字符可以加入到以 i - 1 字符为结尾的最长不含重复字符的子字符串中，即此时有 dp[i] = dp[i - 1] + 1 ，比如说当前字符串为 abcde ，此时 e 为 x ，e 未曾在之前的字符串中出现，那么将其加入到以 d 结尾的子字符串中，不会打破原来的不重复规则。2、如果找到了一个不为 -1 的 index ，那么证明 x 字符在 [0, i - 1] 位置内出现过，如果：dp[i - 1] < i - index ，此时说明字符 s[index] 在子字符串 dp[i - 1]区间之外，此时将 s[i]加入到以 s[i - 1]为结尾的最长不重复子串中，不会破坏规则，此时 dp[i] = dp[i - 1] + 1，比如说对于字符串 axxbcda 中，s[i] = 'a'，而前一个 ‘a’ 出现在dp[i - 1]的最长不重复子串之外，所以将 s[i] 加入到 s[i - 1]结尾的最长不重复子串中不会破坏规则。dp[i - 1] >= i - index，说明字符串 s[index]在子字符串 dp[i - 1] 的区间之内，所以此时以 s[i] 为结尾的最长不重复子串的长度由 s[index]中 index 的位置决定，即dp[i] = i - index。3、我们使用一个 Map 来保存字符 s[i] 的上一个出现位置，如果不存在，那么返回 -1 ，在循环过程中，需要更新这个 Map。3、解题代码public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) return 0; Map<Character, Integer> memo = new HashMap<>(); // 由于 dp[i] 只与前一个状态 dp[i - 1] 有关，所以使用一个变量进行滚动 int temp = 0, result = 0; for (int i = 0;i < s.length();i++) { // 如果没有对应的 key ，那么返回 -1 int index = memo.getOrDefault(s.charAt(i), -1); // 更新 map memo.put(s.charAt(i), i); temp = temp < i - index ? temp + 1 : i - index; result = Math.max(temp, result); } return result; }1.3、把数字翻译成字符串1、题目描述给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。示例一输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"2、解题思路使用动态规划解决这道题。明确 dp 数组的含义。我们设dp[i] 的含义为：下标范围为 [0, i] 的那部分数字有 dp[i] 种翻译方法。明确状态转移方程对于dp[i] 而言，我们需要进行分类讨论。1、当数字中的最后两个数字，即[i - 1, i] 范围的数字可以被翻译为一个数时，0 =< (i - 1) * 10 + i <= 25时，那么我们有两种选择，我们即可以直接将最后一个数字翻译为一个字母，此时存在等式 dp[i] = dp[i - 1] ；又可以将最后两个数字直接翻译成一个字母，此时存在等式 dp[i] = dp[i - 2]。情况 1 需要综合两个选择进行考虑，所以这种情况下 dp[i] = dp[i - 1] + dp[i - 2]。1、当数字中的最后两个数字无法直接被翻译为一个数时，此时我们别无选择，只有将最后一个数直接翻译成一个字母，此时存在等式dp[i] = dp[i - 1]。故我们可以得到以下的状态转移方程。if (最后两个数可以翻译为一个字母) { dp[i] = dp[i - 1] + dp[i - 2]; } else { dp[i] = dp[i - 1]; }数组初始化，对于第一个数字，我们只有将它直接转换为一个字母，此时 dp[0] = 1。3、解题代码 public int translateNum(int num) { //1 先将 num 转换为字符串 String str = String.valueOf(num); // 创建一个 dp 数组，长度为 str.length() int[] dp = new int[str.length()]; // 初始化 dp 数组 dp[0] = 1; // 从 1 开始 for (int i = 1;i < str.length();i++) { // 如果前一个数等于 1 ，或者前一个数等于 2 且当前数小于等于 5 if (str.charAt(i - 1) == '1' || (str.charAt(i - 1) == '2' && str.charAt(i) <= '5')) { if (i == 1) { // 如果 i == 1，那么直接初始化为 2 dp[i] = 2; } else { dp[i] = dp[i - 2] + dp[i - 1]; } } else { dp[i] = dp[i - 1]; } } return dp[str.length() - 1]; } 1.4、删除并获得点数1、题目描述给你一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i] ，删除它并获得nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1和nums[i] + 1的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。示例一输入：nums = [3,4,2] 输出：6 解释： 删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。示例二输入：nums = [2,2,3,3,3,4] 输出：9 解释： 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。2、解题思路这道题与打家劫舍的思路差不多，如果我们在原来数组的基础上构造一个新数组，这个数组以 元素的值为下标，nums[i] 表示 i 出现的次数，以示例二的数组为例，构造出来的新数组为：nums = {2,2,3,3,3,4} temp = {0,0,2,3,1}代表原来的数组中有 0 个 0 ，0 个 1 ，2 个 2 ，3 个 3 ，一个 4。这样就变成了打家劫舍问题。dp 数组的含义：其中 dp[i] 表示面对值为 i 的数时，能获得的最大点数为 dp[i]。状态转移方程和打家劫舍一样，我们在选择值为 i 的数时，不需要考虑 i + 1 的数，只需要考虑 i - 1 的情况，此时 dp[i] 有两个选择：1、第一个选择就是选择获取 i - 1 的点数，此时 i 的点数已经不能选择（因为 i 的值），所以此时有式子为 dp[i] = dp[i - 1]。2、第二个选择就是选择获取 i - 2的点数，此时可以选择 i 的点数，此时存在式子 dp[i] = dp[i - 2] + i * temp[i]。所以状态转移方程如下：dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * temp[i]);数组初始化和打家劫舍的 dp 数组初始化一样，但注意这里需要对构造出来的新数组进行初始化。3、解题代码public int deleteAndEarn(int[] nums) { if (nums == null || nums.length == 0) return 0; //1 先找出数组中的最大数，用于构造新数组 int max = Integer.MIN_VALUE; for (int num : nums) { max = Math.max(max, num); } if (max <= 0) return 0; // 必须是最大值 + 1 长度 int[] temp = new int[max + 1]; for (int num : nums) { temp[num]++; } // 接下来，就按照打家劫舍的方法做 if (temp.length == 1) return temp[0]; if (temp.length == 2) return Math.max(temp[0], temp[1]); int one = temp[0]; int two = Math.max(temp[0], temp[1]); int cur = 0; for (int i = 2;i < temp.length;i++) { cur = Math.max(two, one + i * temp[i]); one = two; two = cur; } return cur; }1.5、接雨水1、题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。2、解题思路dp 数组的含义，其中 dp[i] 表示在下标为 i 的柱子上可以装的水。我们设第 i 根柱子左边最高的柱子高度为 maxLeft， 同时记第 i 根柱子右边最高的柱子高度为 maxRight ，则第 i 根柱子上能承载的水量为：dp[i] = Math.max(0, Math.min(maxLeft, maxRight) - height[i])如果我们每次都需要向左右两边遍历找寻最大值，那么时间复杂度就会非常高。创建两个长度为 n 的数组 leftMax 和 rightMax ， 对于 0 <= i < n ，leftMax[i]表示下标 i 及其左边的位置中，height的最大高度；而 rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。1、leftMax[0] = height[0]， rightMax[n - 1] = height[n - 1]。2、当 1 <= i <= n - 1 时，leftMax[i] = Math.max(leftMax[i - 1], height[i])。3、当 0 <= i <= n - 2 时，rightMax[i] = Math.max(rightMax[i - 1], height[i])。因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。这道题中，我们不需要使用到 dp 数组，只需要使用一个变量进行保存同时累加即可。状态转移方程我们设在第 i 根柱子上能存的水为 count ，则：int count = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i])3、解题代码public int trap(int[] height) { if (height == null || height.length <= 2) return 0; int[] leftMax = new int[height.length]; leftMax[0] = height[0]; // 正向遍历，获取每根柱子左边的最大高度 for (int i = 1;i < height.length;i++) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } int[] rightMax = new int[height.length]; // 反向遍历，获取每根柱子右边的最大高度 rightMax[height.length - 1] = height[height.length - 1]; for (int i = height.length - 2;i >= 0;i--) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } // 使用一个变量来计算总水量 int sum = 0; // 第一根和最后一根柱子没有结果，直接跳过 for (int i = 1;i < height.length - 1;i++) { int count = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]); sum += count; } return sum; }1.6、丑数 II1、题目描述给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。（1 也可以看为一个丑数）。示例一输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。=丑数计算思路由于 1 也是丑数，那么我们可以将 1 作为基础乘以 2,3,5 ，得到的结果也是丑数，再将这些得到的结果分别乘以 2,3,5 ，得到的结果也都是丑数，然后按照从小到大取到第 n 个结果，就是第 n 个丑数：2、解题思路使用最小堆在这个解决思路中，我们需要创建一个小顶堆和一个集合，其中集合用于取出重复的丑数，比如说上图中生成的丑数存在相同的情况，我们需要进行去重。初始化时，最小堆中只存在丑数 1。循环遍历，将 1 从最小堆中取出，然后将 1 乘以三个质因子，然后将结果放入最小堆中（需要先到集合中看一下有没有这个元素，如果有那么就不加入到最小堆中）。不断从堆中取出元素，然后乘以质因子，再将没出现过的结果放入到最小堆中，循环 n 次，拿到的就是第 n 个丑数。动态规划1、dp 数组的含义：其中 dp[i] 表示第 i 个丑数的值，则第 n 个丑数即为 dp[n]。2、状态转移方程：定义三个指针 p2,p3,p5 ，表示下一个丑数是当前指针指向的丑数乘以对应的质因子。初始化时，三个指针的值均为 1 ，当 2 <= i <= n 时，有：dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3),dp[p5] * 5);然后我们需要比较 dp[i] 与 dp[p2] * 2 ，dp[p3] * 3 ，dp[p5] * 5 是否相等，如果相等则将对应的指针 + 1。从上面的图中，当求第二个丑数时，结果从 {2,3,5} 中 诞生，我们得到第二个丑数为 2 ，求第三个丑数时，我们在{3,5,4} 中求结果，可以看到 {3,5} 是上次求丑数留下来的结果，而 4 正是 2 * 2 ，即 1 后移（ + 1）后 * 2 的结果：3、dp 数组初始化：dp[1] 表示第一个丑数，初始化为 1。3、解题代码最小堆这里为了防止溢出，使用的是 Long 型。public int nthUglyNumber(int n) { if (n == 1) return 1; // 创建一个最小堆，用于存放丑数 PriorityQueue<Long> minHeap = new PriorityQueue<>(); // 创建一个数组，用于存放质因子。 int[] nums = {2, 3, 5}; Set<Long> set = new HashSet<>(); // 初始化，我们需要将 1 放入最小堆中 minHeap.add(1L); long result = 0; for (int i = 0;i < n;i++) { result = minHeap.poll(); for (int num : nums) { long uglyNum = num * result; // 只有集合中不存在时，才将结果加入到最小堆中 if (!set.contains(uglyNum)) { minHeap.add(uglyNum); set.add(uglyNum); } } } return (int)result; }动态规划public int nthUglyNumber(int n) { if (n == 1) return 1; int[] dp = new int[n + 1]; dp[1] = 1; int p2 = 1, p3 = 1, p5 = 1; for (int i = 2;i <= n;i++) { dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5); if (dp[i] == dp[p2] * 2) { p2++; } if (dp[i] == dp[p3] * 3) { p3++; } if (dp[i] == dp[p5] * 5) { p5++; } } return dp[n]; }1.7、跳跃游戏 I1、题目描述给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 2、解题思路dp 数组的含义：其中 dp[i] 表示能否到达下标为 i 的位置，所以 dp 应该是一个 boolean 类型的数组。状态转移方程。遍历 [0, i - 1] ，我们需要找到一个位置 j ，如果小人能到达 j 位置且满足条件 j + nums[j] >= i，那么证明 i 是可以到达的，此时我们可以使 dp[i] = true ，然后我们需要跳出循环。if(dp[j] && j + nums[j] > i) { dp[i] = true; }dp 数组的初始化：我们需要初始化 dp[0] = true，因为小人从 0 位置开始，同时需要返回 dp[nums.length - 1]。3、解题代码public boolean canJump(int[] nums) { if (nums == null || nums.length <= 1) return true; boolean[] dp = new boolean[nums.length]; dp[0] = true; for (int i = 1;i < nums.length;i++) { for (int j = 0;j < i;j++) { if (dp[j] && nums[j] + j >= i) { dp[i] = true; break; } } } return dp[nums.length - 1]; }1.8、跳跃游戏 II1、题目描述1、题目描述1、题目描述 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例一输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。2、解题思路dp 数组的含义其中 dp[i] 表示到达 i 位置所用的最小步数，我们需要返回 dp[nums.length - 1]。状态转移方程当我们处于第 i 个位置时，我们遍历 [0. i - 1] 位置，然后寻找在哪个位置可以直接用一步到达 i 位置。if (j + nums[j] >= i) { // 如果在 j 位置可以直接到达 i 位置，那么直接在到达 j 所需要的最少步数 dp[j] 的基础上 + 1即可，但我们需要和 dp[i] 做比较，取最小值 dp[i] = Math.min(dp[i], dp[j] + 1); }=初始化 dp 数组由于在状体转移方程中，我们需要使用 min 函数来选择最小值，那么我们给数组的初始化值就不能是简单的 0 ，为了方便，我们先将数组中的所有元素全部置为 Integer,MAX_VALUE。当 i 为 0 时，我们只需要 0 步就可以到达，所以 dp[0] = 0。当 i 为 1 时，我们只需要一步就可以到达，所以 dp[1] = 1。3、解题代码public int jump(int[] nums) { int len = nums.length; if (len <= 1) return 0; // 创建一个大小为 len 的数组，并对它的值进行初始化 int[] dp = new int[len]; // 初始化数组的值为 Integer.MAX_VALUE ，因为我们需要与 0 作比较取最小值，所以要初始化一个值 Arrays.fill(dp, Integer.MAX_VALUE); // 初始化 dp[0] 和 dp[1] ，当 i 等于 0 时，至少花 0 步就可以到达，当 i 等于 1 时，只需要一步就可以到达 1 dp[0] = 0; dp[1] = 1; for (int i = 2;i < len;i++) { for (int j = 0;j < i;j++) { // 如果在 [0, i - 1] 范围内有位置可以一步到达 i ，那么我们需要进行选择， if (j + nums[j] >= i) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[len - 1]; }1.9、环形子数组的最大和1、题目描述给定一个由整数数组 A 表示的**环形数组 C**，求 C 的非空子数组的最大可能和。 在此处，环形数组意味着数组的末端将会与开头相连呈环状。 （形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]） 此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。 （形式上，对于子数组 C[i], C[i+1], …, C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）示例一输入：[1,-2,3,-2] 输出：3 解释：从子数组 [3] 得到最大和 3示例二输入：[5,-3,5] 输出：10 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10示例三输入：[3,-1,2,-1] 输出：4 解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 42、解题思路1、对于一个环形数组来说，它的最大连续子数组其实只有两种情况：第一种，最大连续子数组分布在数组中间，比如说下面的情况：对于这种情况，我们只需要按照求普通数组的最大连续子数组的和的思路做即可。第二种，最大连续子数组首尾相连，比如说下面的情况：这种情况下，我们要求的值 answer 满足 answer = totalSum - min_so_far，其中 min_so_far表示图中灰色部分的和，即普通数组中最小连续子数组的和，我们可以借由最大连续子数组的和来做。3、解题代码public int maxSubarraySumCircular(int[] nums) { if (nums == null || nums.length == 0) return 0; int first = maxSubarray(nums); int total = 0; // 计算 total 的值 for (int num : nums) { total += num; } int min = minSubarray(nums); int second = total - min; // 如果 total 等于 min ，那么证明差为 0 ，那么此时如果 first 返回的值是负数，那么就会返回错误的 0 if (total == min) return first; return Math.max(first, second); } private int minSubarray(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int len = nums.length; int[] dp = new int[len]; dp[0] = nums[0]; int min = Integer.MAX_VALUE; for (int i = 1;i < len;i++) { dp[i] = Math.min(dp[i - 1] + nums[i], nums[i]); min = Math.min(dp[i], min); } return min; } private int maxSubarray(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int len = nums.length; int[] dp = new int[len]; int max = Integer.MIN_VALUE; dp[0] = nums[0]; for (int i = 1;i < len;i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); max = Math.max(dp[i], max); } return max; }2、乘积最大子数组1、题目描述给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）， 并返回该子数组所对应的乘积。示例一输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。示例二输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。2、解题思路与和最大子数组不一样的是，在本题中，我们需要根据当前遍历的元素来进行更新 dp 数组的值，我们设置两个变量，其中preMax 为 nums[0: i - 1]中最大的乘积，而preMin 为 nums[0: i - 1]中最小的乘积（可能为负数）。当 nums[i]为正数时，此时由于正正得正，我们需要更新 preMax = Math.max(preMax * nums[i], nums[i])，同时更新 preMin = Math.min(preMax * nums[i], nums[i])。当 nums[i]为负数时，此时由于负负为正得正，我们需要更新 preMax = Math.max(preMin * nums[i], nums[i])，同时更新 preMin = Math.min(preMin * nums[i], nums[i])。我们使用一个 max 变量来记录全局最大值，将其与 preMax 比较。3、解题代码public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int preMax = nums[0], preMin = nums[0], max = nums[0]; int curMax = 0, curMin = 0; for (int i = 1;i < nums.length;i++) { if (nums[i] > 0) { curMax = preMax * nums[i]; curMin = preMin * nums[i]; } else { curMax = preMin * nums[i]; curMin = preMax * nums[i]; } preMax = Math.max(curMax, nums[i]); preMin = Math.min(curMin, nums[i]); max = Math.max(preMax, max); } return max; }2.1、乘积为正数的最长子数组长度1、题目描述给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组，请你返回乘积为正数的最长子数组长度。示例一输入：nums = [1,-2,-3,4] 输出：4 解释：数组本身乘积就是正数，值为 24 。示例二输入：nums = [-1,-2,-3,0,1] 输出：2 解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。2、解题思路与上一题相同，我们在遍历到某个元素时，根据这个元素的情况进行判断。确定 dp 数组的含义。我们需要创建两个数组，其中：1、pos[i] 表示以 i 结尾的乘积为正数的最长子数组长度。2、neg[i] 表示以 i 结尾的乘积为负数的最长子数组长度。状态转移方程1、当 nums[i] > 0 时，此时 nums[i] 的值不会影响之前子数组乘积的值的正负：所以，如果 pos[i - 1] 大于 0 ，那么此时它可以放心乘上 nums[i] ，如果 pos[i - 1] 等于 0 ， 那么子数组 {nums[i]} 就是以 i 结尾的乘积为正数的最长子数组，即此时 pos[i] = 1， 所以我们可以直接列出当 nums[i] 大于 0 的状态转移方程； 而如果 neg[i - 1] 大于 0 ，那么它也可以放心乘上 nums[i]，如果 neg[i - 1] 等于 0， 那么 neg[i ] 依然为 0。if (nums[i] > 0) { pos[i] = pos[i - 1] + 1; neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; }2、当 nums[i] < 0 时，此时 nums[i] 的值会影响之前子数组乘积的值的正负：如果 pos[i - 1] 大于 0，那么此时我们将 nums[i] 放入以 i - 1 结尾的子数组中， 整个子数组的乘积变为了负数，所以此时有 neg[i] = pos[i - 1] + 1；如果 pos[i - 1] 等于 0 ， 那么此时如果我们将 nums[i] 放入以 i - 1 结尾的子数组中，可能会导致整个子数组乘积变为正， 所以此时我们直接记 neg[i] 为 1 。 如果 neg[i - 1] 大于 0，那么此时将 nums[i] 放入以 i - 1 结尾的子数组中， 整个子数组的乘积变为了正数，所以此时 pos[i] 的值应该更新为 neg[i - 1] + 1 ， 如果 neg[i - 1] 的值等于 0 ，那么应该将 pos[i] 置为 0。 if (nums[i] < 0) { neg[i] = pos[i - 1] + 1; pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; }所以，我们可以得出状态转移方程如下：if (nums[i] > 0) { pos[i] = pos[i - 1] + 1; neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; } else if (nums[i] == 0) { pos[i] = neg[i] = 0; } else { neg[i] = pos[i - 1] + 1; pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; }dp 数组的初始化。这个需要根据 nums[0] 的值进行判断。1、当 nums[0] 大于 0 时， pos[0] = 1，neg[0] = 0。2、当 nums[0] 等于 0 时，直接初始化为 0。3、当 nums[0] 小于 0 时，neg[0] = 1，pos[i] = 0。3、解题代码public int getMaxLen(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0] > 0 ? 1 : 0; int[] pos = new int[nums.length]; int[] neg = new int[nums.length]; int max = Integer.MIN_VALUE; if (nums[0] > 0) { pos[0] = 1; } else if (nums[0] < 0) { neg[0] = 1; } for (int i = 1;i < nums.length;i++) { if (nums[i] > 0) { pos[i] = pos[i - 1] + 1; neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; } else if (nums[i] == 0) { pos[i] = 0; neg[i] = 0; } else { neg[i] = pos[i - 1] + 1; pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; } max = Math.max(max, pos[i]); } return max; }由于在状态转移方程中， dp[i] 的值只与前一个状态相关，所以我们可以使用一个变量进行滚动更新：public int getMaxLen(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0] > 0 ? 1 : 0; int posMax = 0; int negMax = 0; int max = Integer.MIN_VALUE; if (nums[0] > 0) { posMax = 1; } else if (nums[0] < 0) { negMax = 1; } int curPos = 0; int curNeg = 0; for (int i = 1;i < nums.length;i++) { if (nums[i] > 0) { curPos = posMax + 1; curNeg = negMax > 0 ? negMax + 1 : 0; } else if (nums[i] == 0) { curPos = 0; curNeg = 0; } else { curNeg = posMax + 1; curPos = negMax > 0 ? negMax + 1 : 0; } // 进行滚动 negMax = curNeg; posMax = curPos; max = Math.max(max, curPos); } return max; }背包1.1、背包回顾1、题目描述有 N 件物品和一个最多能负重 W 的背包，其中第 i 件物品的重量是 weight[i]， 价值是 value[i]。每件物品只能使用一次，求解将哪些物品装入背包里， 得到的物品价值总和最大？2、使用动态规划求解明确选择和状态在这个问题中，状态包含两个变量，即背包的重量及所得到的价值，而选择也非常简单，就是是否选择将某件物品放入背包中。明确 dp 数组的含义，这里使用一个二维的 dp 数组来解决这个问题，其中 dp[i][j] 表示从下标 [0, i] 的物品中任意取，放入容量为 j 的背包中，所能获得价值的最大总和为多少明确递推公式1、对于第 i 件物品，当剩余背包容量无法容纳该物品，或者我们选择不将其放入到背包中时，此时有关系如下：dp[i][j] = dp[i - 1][j]2、对于第 i 件物品，当剩余背包容量可以容纳该物品，且我们选择将其放入到背包时，此时存在关系如下，其中 weight[i] 、 value[i ] 分别指 i 物品的重量与价值。dp[i][j] = dp[i - i][j - weight[i]] + value[i];因此我们可以得到以下的递推公式：if (j < weight[i]) { dp[i][j] = dp[i - 1][j] } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) }初始化 dp 数组1、当 j 为 0 时，此时背包容量为 0 ，因此可获取的最大价值也为 0 ，即 dp[i][0] = 0。2、当 i 为 0 时，即只有第一件物品可供选择时，如果此时背包容量 j >= weight[0] ，那么应该初始化对应的 dp[0][j] 为 value[0]。1.2、使用一维滚动数组优化背包问题1、优化思路当使用二维数组时，背包问题的递推公式为 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。可以看到，如果我们将 dp[i - 1] 那一层都拷贝到 dp[i] 上，那么表达式完全可以是 dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i]] + value[i])。当前层的状态完全由上一层状态推导而来，对于这种情况，我们可以考虑使用滚动数组进行优化，这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。2、含义介绍确定 dp 数组的含义在一维 dp 数组中， dp[j] 表示：容量为 j 的背包，所背的物品价值可以最大为 dp[j]。确定递推公式1、当我们选择不放物品 i 时，所得到的最大价值为 dp[j]，这里可以类比我们使用二维数组的时候，如果选择不放物品 i 时，我们得到的最大价值为 dp[i - 1][j] ， 等于是把 dp[i][j] 的上一层数据拷贝下来。2、当我们选择放物品 i 时，所得到的最大价值为 dp[j - weight[i]] + value[i]。所以，我们可以得到使用一维数组时，01 背包问题的递推公式为：if (j < weight[i]) { dp[j] = dp[j]; } else { dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); }dp 数组初始化当 j 为 0 时，此时背包容量为 0 ，所以所能装的物品的最大价值也是 0 ，即 dp[0] = 0； 对于其他位置的值，我们同样将其初始化为 0 ， 避免因初始化值过大导致递推公式计算出来的值无法将初始值覆盖（将整个数组都初始化为 0 。 遍历顺序在二维数组中，无论是先遍历物品，还是先遍历背包都是可以的， 但是在一维 dp 数组中，我们需要先遍历物品，然后再遍历背包， 同时需要注意的是，我们在遍历背包时，需要进行倒序遍历。 为什么要倒序遍历背包？这是为了保证物品只被添加一次，在使用二维数组时， 当前层和上一层的数据是完全隔离开的，所以正序遍历和倒序遍历都可以， 但当我们使用一维数组时， 如果先计算 dp[j - 1] ，那么它可能会影响到后面 dp [j] 的数据， 我们可以来举一个例子，其中 weight = {1,3,4} ，values = {15,20,30} ，同时最大容量 capacity = 4。 1、当我们使用正序遍历时， dp[1] = Math.max(dp[1], dp[1 - weight[0]] + values[0]) = Math.max(dp[1], dp[1 - 1] + 15) = 15; dp[2] = Math.max(dp[2], dp[2 - weight[0]] + values[0]) = Math.max(dp[2], dp[2 - 1] + 15) = 30。可以看到，如果我们使用正序遍历，那么在计算 dp[2] 时，递推公式中的 dp[2 - 1] = dp[1]是我们在上一次计算出来的 15 ，而且得到的结果也是 30 ，这相当于我们将第 0 件物品重复加入到了背包中。1、当我们使用倒序遍历时， dp[2] = max(dp[2], dp[2 - weight[0]] + values[0]) = max (0, dp[1] + 15) = 15；dp[1] = max(dp[1], dp[1 - weight[0]] + values[0]) = max(0, dp[0] + 15) = 15。此时可以看到，第 0 件物品只被加入到了一次，这是因为此时在计算 dp[j] 时， dp[j - 1]的结果还没有被计算出来，所以不会影响 dp[j]的计算。3、解题代码public static int knapsack(int number, int capacity, int[] weight, int[] values) { if (weight == null || values == null || weight.length != values.length) return 0; // 创建一个一维的 dp 数组，dp[j] 表示，当背包容量为 j 时，该背包能容纳物品的最大价值 int[] dp = new int[capacity + 1]; // 外层循环，先遍历物品 for (int i = 0;i < number;i++) { // 内层循环，需要倒序遍历背包 for (int j = capacity;j >= weight[i];j--) { // 使用递推公式，从右至左计算 dp[j] 的值 dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); } } // 最后返回 dp[capacity] ，就是 capacity 容量的背包所能容纳的物品的最大价值 return dp[capacity]; }1.3、目标和1、题目描述给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。示例一输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3示例二输入：nums = [1], target = 1 输出：12、解题思路使用动态规划来解决这道题，这道题也可以转换为 01 背包问题，与 01 背包问题不同的是，前者可以选择是否将这件物品装入背包中，而本题要求全部数字都被选中，但可以选择+ 和-。将这个数组分割为两部分，其中被赋予 + 的那一部分称为 P ，而被赋予 - 的那一部分称为N，所以我们可以得到以下结论。1、sum(P) - sum(N) = S。2、sum(P) + sum(N)= 数组中所有元素的和 sum。3、将上面的式子相加，有 2 * sum(P) = target + sum，移项有 sum(P) = (target + sum) / 2，我们记这个值为 result，即 result = (target + sum) / 2。所以问题就转换为求容量为 result 的 01 背包问题，要装满容量为 result 的背包，有几种方案：如果 target 的值大于 sum ，那么直接返回 0 ，因为此时无法找到一种可能的实现。如果 sum§ 不是正数，即 (target + sum) 不是偶数，那么返回 0。确定 dp 数组的含义dp[j] 表示在数据 nums 中，凑出 j 的方法有 dp[j] 种，换成背包问题就是，如果要填充 j 这么大容积的包，有 dp[j] 种方法。确定递推公式1、填满容量为 j - nums[i] 的背包，有 dp[j - nums[i]] 种方法。2、那么只需要获得 nums[i] ，我们就可以凑出 dp[j] ，此时得到 dp[j] 的方法有 dp[j - nums[i]] ，这里有点类似凑硬币。比如说，如果我们当前需要计算 dp[5] ，同时我们手中有一个重量为2的物品，此时我们只需要计算出 dp[3] 就可以得到在我们有 重量为 2的物品的前提下，能填满容量为5的背包的方法，所以我们可以得到以下的递推公式。dp[j] += dp[j - nums[i]]1初始化 dp 数组这道题中，由于我们要求 dp[result] ，所以我们需要初始化一个长度为result + 1 的数组，同时，当 j == 0 时，使用 nums 数组中的元素可以有一种方法凑出 0 ，故 dp[0] = 1 ;3、解题代码这里使用一维滚动数组来解这道题。public int findTargetSumWays(int[] nums, int target) { if (nums == null || nums.length == 0) return 0; //1 计算数组元素和 int sum = gengerateSumByArray(nums); //2 如果 sum 小于 target 或者 （sum + target） 不是偶数，那么直接返回 0 if (sum < target || (sum + target) % 2 == 1) return 0; //3 使用一个变量保存 (sum + target) / 2; target = (sum + target) / 2; //这里需要进行判断，如果计算出来的 target 小于 0 ，那么需要将其变为相反数 target = Math.abs(target); //4 创建一个长度为 target + 1 的数组，并进行初始化 int[] dp = new int[target + 1]; // 当 j == 0 时，此时在 nums 中，只能找出一种方案凑出 0 ，所以 dp[0] = 1 dp[0] = 1; //5 外层循环遍历物品 for (int num : nums) { //6 内层循环倒序遍历背包 for (int j = target;j >= num;j--) { // 使用递推公式累加 dp[j] 的值 dp[j] += dp[j - num]; } } return dp[target]; } private int gengerateSumByArray(int[] nums) { int sum = 0; for (int num: nums) sum += num; return sum; }1.4、使用一维滚动数组优化分割等和子集问题1、优化思路使用一维滚动数组代替原来的二维数组dp 数组的含义dp 是一个一维的 boolean 数组，其中 dp[j] 表示在数组中，是否可以找到一个子集，使得这些子集的和等于 j。递推公式当我们知道数组元素 nums[i] 时，此时如果 dp[j] 或 dp[j - nums[i]] 有一个为 true ，那么就代表 dp[j] 为 true ，即：dp[j] = dp[j] || dp[j - nums[i]]2、解题代码/** * 这道题可以看为，在 nums 中，是否可以找到几个数，这几个数的和为 sum / 2 ，其中 sum 为数组元素和 */ public boolean canPartition(int[] nums) { if (nums == null || nums.length == 0) return true; //1 计算数组元素和 int sum = gengerateSumByArray(nums); // 如果数组元素和不是一个偶数，那么直接返回 false if (sum % 2 != 0) return false; int target = sum / 2; //2 我们需要在数组 nums 中，找到是否存在几个数字，满足这几个数字的和为 target // dp[j] 表示在数组 nums 中，是否存在几个数字，满足这几个数字的和为 j boolean[] dp = new boolean[target + 1]; // 初始化 dp 数组，当 j == 0 时，此时可以找到几个数字，满足这几个数字的和为 0 dp[0] = true; for (int num : nums) { for (int j = target;j >= num;j--) { // 如果 dp[j] 或 dp[j - num] 有一个为真，那么 dp[j] 即为真，此时代表存在... dp[j] = dp[j] || dp[j - num]; } } return dp[target]; } private int gengerateSumByArray(int[] nums) { int sum = 0; for (int num : nums) sum += num; return sum; }1.5、最后一块石头的重量 II1、解题思路在上面有提到，这道题其实就是尽量将石头分成重量相同的两堆，然后让相撞之后剩下的石头最小。 这道题其实就是求，给你一个大小为 sum / 2 的背包，其中 sum 为 nums 的元素和， 然后尽可能地往背包中装东西，我们假设最多往背包中装了 maxWeight 重量的石头， 那么我们要求的结果就是 sum - 2 * maxWeight;确定 dp 数组使用一个一维的 boolean 类型的 dp 数组， 其中 dp[j] 的含义、状态转移方程与 分割等和子集 问题中 dp 数组的含义相同，即在数组 nums 中， 能否找到一个子集，使得这个子集的元素和的值等于 j 。 当计算好 dp 数组后，我们需要反向遍历 dp 数组，寻找第一个为 true 的元素值，然后得到结果并返回，结果为 sum - 2 * j。2、解题代码public int lastStoneWeightII(int[] stones) { if (stones == null || stones.length == 0) return 0; int sum = generateSumByArray(stones); // 计算出 target 的值，我们要尽可能装满这个容量为 target 的包 int target = sum / 2; boolean[] dp = new boolean[target + 1]; dp[0] = true; // 外层循环遍历物品 for (int stone : stones) { // 内层循环反向遍历背包 for (int j = target;j >= stone;j--) { dp[j] = dp[j] || dp[j - stone]; } } // 填完表后，我们需要找到最接近 target 的一个 j 值 for (int j = target;;j--) { // 找到第一个为 true 的j if (dp[j]) { return sum - 2 * j; } } } private int generateSumByArray(int[] stones) { int sum = 0; for (int stone : stones) sum += stone; return sum; }1.6、一和零1、题目描述给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。示例 一输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。示例 二输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。2、解题思路这道题也可以看为 01 背包问题，其中字符串数组中的每一个字符串都是一件物品，而 m 和 n 相当于一个二维的背包。确定 dp 数组的含义，这里使用滚动数组进行优化，其中 dp[i][j]表示最多有 i 个 0 和 j 个 1 的 strs 的最大子集的大小为 dp[i][j]。对于 dp[i][j]而言，它可以由前一个 strs 里的字符串推导出来，假设该字符串中含有 zeroNum 个 0 ，同时含有 oneNum个 1 ，那么有以下的递推公式。dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)如何初始化 dp 数组？只需要将 dp 初始化为 0 即可:3、解题代码public int findMaxForm(String[] strs, int m, int n) { if (strs == null || strs.length == 0) return 0; // 创建一个二维数组，其中 dp[i][j] 表示子集最多能有 i 个 0 ，j 个 1 时，最大子集的长度 int[][] dp = new int[m + 1][n + 1]; // 外层循环遍历物品，在这道题中，一个字符串就是一件物品 for (String str : strs) { // 获取这个字符串中 1 的个数和 0 的个数 int zeroNum = countCharNum(str, '0'); int oneNum = countCharNum(str, '1'); // 内层循环遍历背包，这里有两个背包需要进行遍历，分别为容量为 m 的背包和 容量为 n 的背包，倒序遍历 for (int i = m;i >= zeroNum;i--) { for (int j = n;j >= oneNum;j--) { // 使用递推公式计算 dp[i][j] 的值 dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); } } } return dp[m][n]; } private int countCharNum(String str, char ch) { int num = 0; for (int i = 0;i < str.length();i++) { if (str.charAt(i) == ch) { num++; } } return num; }完全背包问题1.1、完全背包问题理论说明1、题目描述设有 n 种物品，每种物品都有一个重量及一个价值，其中第 i 件物品的重量为 weight[i]，价值为 value[i]。且每种物品的数量是无限的，同时有一个背包，最大载重量为M ，今从 n 种物品种选取若干个物品（同一种物品可以被多次选取）放入背包中，使其重量的和小于等于 M ，而价值的和为最大。与 01 背包不同的是，前者每件物品只有一个，而完全背包问题中每种物品可以有无限多个。2、解题思路在完全背包问题中，对于第 i 件物品，我们有几种选择：1、选择将 0 个物品装入到背包中。2、选择将 n 个该物品装入到背包中，我们可以不断往背包中添加该物品，直到背包被装满，也就是说，在完全背包问题中，同一件物品被装入背包的次数是有上下限的，下限为 0 ，上限为 M / n （向下取整）。当前背包容量为 j 时，对于第 i 件物品装入背包的次数范围为 [0, j / w[i]] ，其中 j / w[i] 需要向下取整。在之前使用一维滚动数组优化 01 背包问题时，我们有谈及到为什么内层循环需要进行反向遍历 – 为了避免一个物品被重复添加到背包中多次；而完全背包问题里的物品完全可以多次添加到背包中，所以对于完全背包问题的内层循环，我们可以正序遍历背包。3、解题代码/** * 求解完全背包问题 * @param number 物品个数 * @param capacity 背包容量 * @param weight 物品重量数组 * @param value 物品价值数组 * @return 能获取到的最大收益 */ public int completeBackpack(int number, int capacity, int[] weight, int[] value) { if (weight == null || value == null || weight.length != value.length) { return 0; } // 创建一个一维数组 dp int[] dp = new int[capacity + 1]; // 外层数组遍历物品 for (int i = 0;i < number;i++) { // 内层物品遍历背包，这里需要从左往右遍历 for (int j = weight[i];j <= capacity;j++) { // 使用递推公式 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } return dp[capacity]; }1.2、零钱兑换1、题目描述给你一个整数数组 `coins` ，表示不同面额的硬币；以及一个整数 `amount` ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 ， 你可以认为每种硬币的数量是无限的。示例一输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1示例二输入：coins = [2], amount = 3 输出：-12、解题思路这个问题可以看为一个完全背包问题，在这道题中，我们需要求解最值问题。确定 dp 数组含义。其中 dp[j] 表示，要想在 coins 中凑出金额为 j 的零钱，最少需要 dp[j] 个硬币。状态转移方程如果我们手一个 coins[i] ，那么我们只需要计算出凑出 j - coins[i] 的最少硬币数，然后 + 1，即可得到凑出 j 的最少硬币数，所以，我们得到的状态转移方程如下：dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1); // 注意，这里需要当子问题有解时才进行状态转移，即 dp[j - coins[i]] 不为 Integer.MAX_VALUE 时初始化 dp 数组1、当 j 为 0 时，此时只需要 0 个硬币就可以凑出，所以 dp[0] = 0;2、当 j 不为 0 时，我们需要将其初始化为一个非常大的数，避免后面在求出一个大于 0 的数时，在经由 Math.min (0, dp[j]) 进行选择时，让 0 覆盖了结果值，比如说，我现在求出了 dp[1] 为 1 ，但是我的 dp[1] 在初始化时初始化为 0 了，所以导致我在进行取最小值时，无法将 dp[1] = 1 这个值正确地更新到数组中。什么样的子问题才需要进行求解？在我们进行遍历时，只有当子问题有解时，我们才考虑进行递推，所以，如果 dp[j - coin] 的值为 Integer.MAX_VALUE ，那么我们没必要进行状态转移，因为此时代表这个问题无解。3、解题代码public int coinChange(int[] coins, int amount) { if (coins == null || coins.length == 0) return -1; if (amount == 0) return 0; // 创建一个 dp 数组，长度为 amount + 1 ，其中 dp[amount] 就是在 coins 数组中，凑出 amount 所需的最少硬币数，也就是我们要求的结果 int[] dp = new int[amount + 1]; // 初始化 dp 数组，dp[0] = 1，这一步可以省略，我们需要将 dp 数组中非 0 位置的元素 初始化为 Integer.MAX_VALUE for (int i = 1;i < dp.length;i++) { dp[i] = Integer.MAX_VALUE; } // 外层遍历，遍历物品，也即硬币 for (int coin : coins) { // 内层遍历，正向遍历背包， for (int j = coin;j <= amount;j++) { // dp[j - coin] 不为 Integer.MAX_VALUE 时，证明此时 j - coin 可以被凑出，即这个问题有解，此时才需要进行求解。 if (dp[j - coin] != Integer.MAX_VALUE) { // 使用状态转移方程求解 dp[j] 的值，这里求得是最小值 dp[j] = Math.min(dp[j], dp[j - coin] + 1); } } } return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount]; }1.3、零钱兑换 II1、题目描述给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 ，假设每一种面额的硬币有无限个。示例一输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1示例二输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。2、解题思路使用动态规划解决这道题，在本题中，由于每一种面额的硬币有无限个，我们将给定的 coins 数组看为物品数组，coins 数组中每个硬币的数额看为物品的重量，我们要做的就是寻找出凑齐 amount 重量的背包的方案数，这是一个完全背包问题。确定 dp 数组的含义dp[j] 指的是，在 coins 数组中，有 dp[j] 种凑出 amount 数值的方案。状态转移方程这是典型的组合问题，当我们手上有一颗数值为 coins[i] 的硬币时，此时我们只需要知道在 coins 中凑出 amount - nums[i] 的方案数，就可以得到该条件下的方案数，所以状态转移方程应该如下：dp[j] += dp[j - nums[i]]初始化 dp 数组，当 j 为 0 时，此时有一种方案可以凑出 0 ，所以：dp[0] = 1;3、解题代码public int change(int amount, int[] coins) { if (coins == null || coins.length == 0) return 0; // 创建一个 dp 数组，其中 dp[j] 表示在 coins 中，能凑出数额为 j 的方案数 int[] dp = new int[amount + 1]; // 初始化 dp 数组，当 j 为 0 时， dp[j] == 1 dp[0] = 1; // 外层遍历，遍历物品 for (int i = 0;i < coins.length;i++) { // 内层遍历，对于完全背包问题，我们需要正向遍历背包 for (int j = coins[i];j <= amount;j++) { // 使用递推公式计算出 dp[j] dp[j] += dp[j - coins[i]]; } } return dp[amount]; }1.4、组合总和 IV1、题目描述给你一个由 不同 整数组成的数组 `nums` ，和一个目标整数 `target` 。 请你从 `nums` 中找出并返回总和为 `target` 的元素组合的个数。 请注意，顺序不同的序列被视作不同的组合。示例 一输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。示例 二输入：nums = [9], target = 3 输出：02、解题思路这道题是典型的完全背包问题，同时求的是排列数，所以外层循环需要遍历背包，内层循环需要遍历物品。确定 dp 数组的含义。dp[i] 表示凑成正整数为 i 的排列个数为 dp[i]。确定递推公式dp[i] 可以由 dp[i - nums[j]] 推导出来，其中dp[i] 考虑了 nums[j] ，而dp[i - nums[j]]不考虑 nums[j]，因为只要得到 nums[j]，排列个数 dp[i - nums[j]]，就是 dp[i]的一部分。我们可以确定递推公式如下：dp[i] += dp[i - nums[j]];初始化 dp 数组由于递推公式为 dp[i] += dp[i - nums[j]] 的缘故，所以 dp[0] 要初始化为 1 ，这样递归其他 dp[i] 时才会有数值基础。这里需要注意， dp[0] 是没有意义的。3、解题代码 public int combinationSum4(int[] nums, int target) { if (nums == null || nums.length == 0) return 0; // 创建一个 dp 数组，其中 dp[i] 表示能在 nums 中能组成 i 的排列数 int[] dp = new int[target + 1]; // 初始化 dp[0] = 1 ，这个 dp[0] 是没有含义的 dp[0] = 1; // 外层循环遍历背包 for (int i = 0;i <= target;i++) { // 内层循环遍历物品 for (int j = 0;j < nums.length;j++) { // 只有当背包容量大于第 j 件物品时，才需要进行分割子问题 if (i >= nums[j]) { dp[i] += dp[i - nums[j]]; } } } return dp[target]; }1.5、爬楼梯1、题目描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例一输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例二输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶2、解题思路使用完全背包的思路解决这道题，这道题又是一道排列数的问题。此时，背包中只有两件物品，即 1 和 2 ，我们需要找出装满容量为 n 的背包的方案数。确定 dp 数组的含义。其中 dp[i] 表示爬上 n 阶楼梯有 dp[i] 种不同的排列方案。确定递推公式由于此时球的是排列方法，所以我们可以得到本体的递推公式：dp[i] += dp[i - nums[j]];初始化 dp 数组与上题相同，由于此时递推公式是 dp[i] += dp[i - nums[j]] ，所以我们需要初始 dp[0] = 1 ，这是递推的基础值。本题中的物品在本题中，只有两个物品，其中第一个物品的重量为 1 ，第二个物品的重量为 2。3、解题代码public int climbStairs(int n) { if (n == 1 || n == 2) return n; // 初始化一个 dp 数组，长度为 n + 1，其中 dp[i] 表示爬上 i 阶楼梯的方案排列数 int[] dp = new int[n + 1]; // 初始化 dp 数组 dp[0] = 1; // 外层循环，在求排列的过程中需要遍历背包 for (int i = 0;i <= n;i++) { // 内层循环，需要遍历物品，这里只有两件物品，其中第一件物品的重量为 1 ，第二件物品的重量为 2 for (int j = 1;j <= 2;j++) { // 如果当前背包的容量大于物品重量，这里为 j if (i >= j) { dp[i] += dp[i - j]; } } } return dp[n]; }1.6、完全平方数1、题目描述给定正整数 n ，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n 。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。示例一输入：n = 12 输出：3 解释：12 = 4 + 4 + 4示例二输入：n = 13 输出：2 解释：13 = 4 + 92、解题思路这道题中，n 可以有多个相同的完全平方数 x^2 组成，也就是说，如果我们将 x 看为背包问题中的物品，那么每个 x 可以被多次加入到背包中。我们可以将这道题转换为，给你一个容量为 n 的背包，同时给你一些物品，而物品由 n 决定，物品为 [1, b] ，其中满足 b * b <= n 且 (b + 1) * (b + 1) > n。明确 dp 数组含义。其中 dp[j] 表示 j 最少可以由 dp[j] 个完全平方数组成。确定状态转移方程，这道题是一道求最值问题，所以状态转移方程为：dp[j] = Math.min(dp[j], dp[j - i * i] + 1);当我们手中握有 i * i 这个平方数时，我们只需要求出组成 j - i * i 最少需要多少个平方数，然后再这个结果的基础上加上一，就得到了我们想要的结果。初始化 dp 数组1、dp[0] 可以由 0 个平方数组成，所以 dp[0] = 0。2、dp[1] 可以由一个平方数组成，所以dp[1] = 1。3、对于其他下标的元素，在使用递推公式进行运算时，我们不希望它的真正结果被 0 覆盖，所以我们将其他下标的值都初始化为 Integer.MAX_VALUE。在进行子问题分割时，只有当 dp[j - i * i] 不为 Integer.MAX_VALUE 时（此时子问题存在有效解），才进行递推公式的计算。3、解题代码private int getSizeByN(int n) { int size = 0; // 比如说 size 为 10 ，那么比 10 小的平方数有 1、4和9，可供选择的物品有 1 2 3 while (true) { // 如果 size + 1 的平方大于 n ，那么此时直接 break ，得到的 size 就是我们要寻找的值，当前物品的个数就是 1 - n if ((size + 1) * (size + 1) > n) { break; } size++; } return size; }使用两个循环来解决这道题，先遍历物品后遍历背包，只有当当前背包容量大于 i * i 且子问题有效时，才能进行状态转移。public int numSquares(int n) { if (n == 1) return 1; // 创建一个 dp 数组，其中 dp[i] 表示和为 i 的完全平方数的最少数量 int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); // 初始化 dp 数组 dp[0] = 0; // 计算出当前物品的个数，即 size int size = getSizeByN(n); // 外层循环遍历物品 for (int i = 1;i <= size;i++) { // 内层循环正序遍历背包，只有当当前背包容量大于等于物品重量的平方时且子问题有解时，才能进行状态转移 for (int j = 0;j <= n;j++) { if (j >= i * i && dp[j - i * i] != Integer.MAX_VALUE) { // 此时可以进行状态转移 dp[j] = Math.min(dp[j], dp[j - i * i] + 1); } } } return dp[n]; }背包问题总结背包问题大体的接替模板是两层循环，分别是外层循环遍历物品，然后内层循环遍历背包，然后在循环中写状态转移方程。在我现在的学习中，背包问题可以根据所给条件和待求项分为以下几类：1.1、根据所给条件分类根据所给物品的个数，可以分为 01 背包问题和完全背包问题，在使用一维数组进行空间优化时，二者的区别是内层循环的遍历顺序，其中：对于 01 背包问题而言，内层循环在遍历背包时需要逆序遍历，保证物品只被加入到背包中一次。对于完全背包问题而言，内层循环在遍历背包时需要正序遍历。1.2、根据待求项分类1、最值问题 I问背包最多能装多少，状态转移方程一般如下：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);**2、存在问题**当我们求解存在问题时，状态转移方程一般如下：dp[j] = dp[j] || dp[j - nums[i]];比如说上面我们就是将 分割等和子集 、 最后一块石头重量 II 看为存在问题解决。3、组合问题当我们求解存在问题时，状态转移方程一般如下：dp[j] += dp[j - nums[i]];比如说上面提到的零钱兑换 II 、 目标和 就是这类问题。4、最值问题 II问装满背包所有物品的最小个数，状态转移方程一般如下：dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);零钱问题 I 就是这样的问题。1.3、组合问题和排列问题1、组合问题组合数的概念：从 n 个不同元素中，任取 m（m≤n）个元素不计顺序的组成一组，则所有不同的组合个数，称为组合数。如果求组合数，那么就是外层循环遍历物品，内层循环遍历背包。2、排列问题排列数的概念：从 n 个不同元素中，任取 m（m≤n）个元素有顺序的排成一列，则所有不同的排列个数，称为排列数。如果求组合数，那么就是外层循环遍历背包，内层循环遍历物品。编辑距离问题总结在使用动态规划求解字符串相关问题时， dp[i][j] 的含义通常是指字符串 s1 下标范围为 [0. i - 1] 的子串 a ，与字符串 s2 下标范围为 [0, j - 1] 的子串 b ，二者之间的某些指标。个人觉得是为了考虑空串，同时为了 初始化工作的方便。1.1、判断子序列dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为[0, i - 1] 的子串 a ，是否为字符串 t 中范围下标为[0, j - 1]的字符串 b 的子序列， dp 数组是一个二维的boolean 数组。当s[i - 1] == t[j - 1]时，此时表示 s 与 t 找到了一个公共字符，此时我们只需要判断当前 s 的子串 a ，在去掉公共字符后，是否为去掉公共字符的 b 的子序列即可（其中 b 为 t 的子串）。此时 s[0, i - 1] 是否为 t[0, j - 1]的子序列，这个结果完全由 s[0, i - 2] 与 t[0, j - 2]的关系决定。如果此时 a 是 b 的子序列，那么证明s[0, i - 1] 是 t[0, j - 1]的子序列；反之则不是。当s[i - 1] != t[j - 1]，此时我们需要删去 t 子串中的最后一个字符 t[j - 1] ，因为此时 s[0, i - 1] 是否为 t[0,j - 1]的子序列与t[j - 1]完全没有关系。如果 s[0, i - 1] 已经是 t[0, j - 2] 的子序列，那么 s[0, i - 1] 也必定为 t[0, j - 1] 的子序列。如果 s[0, i - 1] 已经是 t[0, j - 2] 的子序列，那么 s[0, i - 1] 也必定为 t[0, j - 1] 的子序列。 如果 s[0, i - 1] 并不是 t[0, j - 2] 的子序列， 那么此时 t[j - 1] 这个字符于事无补，所以 s[0, i - 1] 也一定不为 t[0, j - 1] 的子序列。本题递推公式if (s[i - 1] == t[i - 1]) { dp[i][j] = dp[i - 1][j - 1] } else { dp[i][j] = dp[i][j - 1] }1.2、不同的子序列dp 数组含义：dp[i][j]表示字符串 s 中范围下标为[0, i - 1]的子串 a ，在字符串 t 中范围下标为[0, j - 1]的字符串 b 中作为子序列出现的次数，dp 数组是一个二维的 int 数组。当 s[i - 1] == t[j - 1] 时，此时出现了公共字符，那么我们有两个选择：1、第一个选择就是让 s[i - 1] 字符直接与 t[j - 1]进行匹配，比如说 s = bag , t = baagg，我们可以选择让 t 中的最后一个 g 与 s 的最后一个 g 进行匹配，这是其中一种选择，这种选择下得到的个数为dp[i][j] = dp[i - 1][j - 1] ，即我们只需要查找 s[0, i - 2]在t[0,j - 1] 中作为子序列出现的次数即可。2、第二种选择就是让 s[i - 2]字符与 t[j - 1]进行匹配，而 s[i - 1]不参与匹配，比如说s = bag,t = baagg ，让 t 中倒数第二个 g 与 s 中的最后一个 g 进行匹配，这也是其中一种情况，这种情况下得到的个数为 dp[i][j] = dp[i][j - 1]，我们需要查找 s[0. i - 1] 在t[0, j - 2]中作为子序列出现的次数。由于本题中我们需要求出所有情况下出现次数之和，所以我们需要将上面两种选择得到的结果进行汇总。当 s[i - 1] != t[j - 1] 时，此时我们只能舍弃 t 中最后一个字符，然后用剩下的字符进行匹配，此时式子为 dp[i][j] = dp[i][j - 1]。递推公式if (s[i - 1] == t[i - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + 2); }1.3、两个字符串中的删除操作dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为 [0, i - 1]的子串 a ，变为字符串 t 中范围下标为 [0, j - 1]的子串 b ，所需要进行的删除操作次数。当 s[i - 1] == t[j - 1]时，此时我们此刻相等的字符为公共字符，从a[0, i - 1] 变为 b[0, j - 1]所需的最小删除次数与a[0, i - 2]变为b[0. j - 1]所需的最小删除次数相等，也就是说，公共字符的存在与否并不会对两个字符串的最小删除次数造成影响，所以我们可以得出此时的式子为 dp[i][j] = dp[i - 1][j - 1]。当s[i - 1] == t[j - 1]时，此时我们用三种做法可供选择，此时我们假设 s 的子串为 a ，t 的子串为 b。1、删去 a 中的某一个字符，此时得到的式子为 dp[i - 1][j] + 1，1 表示删去 a 中字符的那一次操作。2、删去 b 中的某一个字符，此时得到的式子为 dp[i][j - 1] + 1 ，1 表示删去 b 中字符的那一次操作。3、同时删去 a 和 b 中的字符，此时得到的式子为 dp[i - 1][j - 1] + 2。由于我们要求最小删除次数，所以我们需要在上述的三种情况中选择一个最小的结果。递推公式if (s[i - 1] == t[i - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; }1.4、编辑距离dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为 [0, i - 1] 的子串 a ，与字符串 t 中范围下标为 [0, j - 1] 的子串 b 之间的最小编辑距离。当 s[i - 1] == t[j - 1] 时，此时子串 a 和 子串 b 二者的编辑距离与去掉公共字符的编辑距离相等，即 dp[i][j] = dp[i - 1][j - 1]。当 s[i - 1] == t[j - 1] 时，此时我们有几种做法可供选择：1、word1 删除一个元素，那么就是以下标 word1[0, i - 2] 与 word2[0, j - 1]的最短编辑距离，再加上一个删除操作，此时得到的式子应该为 dp[i - 1][j] + 1。2、word2 删除一个元素，那么就是以下标 word1[0, i - 1] 与 word2[0. j - 2] 的最短编辑距离，再加上一个删除操作，此时得到的式子应该为dp[i][j - 1] + 1。3、替换元素，此时 word1 替换 word1[i - 1] ，使其等于 word2[j - 1] ，此时我们又可以将 word1[i - 1]看为一个公共元素，只不过我们需要原来的基础上加上一次编辑，此时得到的式子为 dp[i - 1][j - 1] + 1。4、对于添加操作来说， word1 添加一个字符，就相当于 word2 删除一个字符，比如说，当 word1 为 abce ，word2 为 abc 时，word1 删去 e 与 word2 加上 e 的结果都相同，所以我们只需要考虑删除的情况即可。递推公式if (s[i - 1] == t[i - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; }

数据结构与算法学习——动态规划-3目录博主介绍前言1、礼物的最大价值1.2、最长不含重复字符的子字符串1.3、把数字翻译成字符串1.4、删除并获得点数1.5、接雨水1.6、丑数 II1.7、跳跃游戏 I1.8、跳跃游戏 II1.9、环形子数组的最大和2、乘积最大子数组2.1、乘积为正数的最长子数组长度背包1.1、背包回顾1.2、使用一维滚动数组优化背包问题1.3、目标和1.4、使用一维滚动数组优化分割等和子集问题1.5、最后一块石头的重量 II1.6、一和零完全背包问题1.1、完全背包问题理论说明1.2、零钱兑换1.3、零钱兑换 II1.4、组合总和 IV1.5、爬楼梯1.6、完全平方数背包问题总结1.1、根据所给条件分类1.2、根据待求项分类1.3、组合问题和排列问题编辑距离问题总结1.1、判断子序列1.2、不同的子序列1.3、两个字符串中的删除操作1.4、编辑距离💫点击直接资料领取💫目录博主介绍💂 个人社区:CSDN全国各地程序猿🤟作者介绍：中国DBA联盟(ACDU)成员，CSDN全国各地程序猿（媛）聚集地管理员。目前从事工业自动化软件开发工作。擅长C#、Java、机器视觉、底层算法等语言。2019年成立柒月软件工作室，2021年注册苏州凯捷智能科技有限公司💬如果文章对你有帮助，欢迎关注、点赞、收藏（一键三连）和C#、Halcon、python+opencv、VUE、各大公司面试等一些订阅专栏哦💅 有任何问题欢迎私信，看到会及时回复👤 微信号：stbsl6，微信公众号：苏州程序大白🎯 想加入技术交流群的可以加我好友，群里会分享学习资料前言🥝数据结构与算法学习——动态规划-1🥝🥝数据结构与算法学习——动态规划-2🥝继续数据结构与算法学习——动态规划-1、动态规划-2讲解1、礼物的最大价值1、题目描述在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？示例一输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物2、解题思路确定 dp 数组的含义其中 dp[i][j] 表示到达棋盘上的 [i , j] 位置时，所能拿到的礼物的总价值。状态转移方程对于棋盘上的某个位置 (i, j) 来说 ，它的状态可以由两个状态得来，即它的上方元素 （i - 1,j） 和左边元素 （i, j - 1） 得到，同时还需要加上当前位置礼物的价值 nums[i][j]，我们需要在上面的选择中取较大值。dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + nums[i][j];初始化 dp 数组我们需要初始化第一行和第一列的元素其中第一行的元素为 nums[0,i]上的元素累加值，比如说，在例子中， dp[0][0]应该初始化为 nums[0][0]，dp[0][1]应该初始化为 nums[0][0] + nums[0][1]，dp[0][2] = nums[0][0] + nums[0][1] + nums[0][2]。同理，第一列的元素也应该按照上面的规则初始化，只不过变为向下累加。遍历顺序这道题是最常规的动态规划问题，我们只需要按照从头到尾的顺序进行遍历即可，可以看到 dp[i][j] 是由上一行、前一列的元素推导出来的。3、解题代码 public int maxValue(int[][] grid) { if (grid == null || grid.length == 0) return 0; int row = grid.length; int column = grid[0].length; int[][] dp = new int[row][column]; int value = 0; // 初始化 dp 数组 for (int i = 0;i < row;i++) { value += grid[i][0]; dp[i][0] = value; } value = 0; for (int j = 0;j < column;j++) { value += grid[0][j]; dp[0][j] = value; } for (int i = 1;i < row;i++) { for (int j = 1;j < column;j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[row - 1][column - 1]; } 1.2、最长不含重复字符的子字符串1、题目描述请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。示例一输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例二输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。2、解题思路明确 dp 数组的含义其中 dp[i] 表示以字符 s.charAt(i) 结尾的最长不含重复字符的子字符串的长度。明确状态转移方程对于 i 位置的字符 x 来说，我们需要找到 x 在 s 中的上一个位置 index ，然后根据 index 来判断下一步该如何选择。1、如果 index == -1 ，此时代表 x 字符串在 [0, i - 1]位置内不曾出现，那么 x 字符可以加入到以 i - 1 字符为结尾的最长不含重复字符的子字符串中，即此时有 dp[i] = dp[i - 1] + 1 ，比如说当前字符串为 abcde ，此时 e 为 x ，e 未曾在之前的字符串中出现，那么将其加入到以 d 结尾的子字符串中，不会打破原来的不重复规则。2、如果找到了一个不为 -1 的 index ，那么证明 x 字符在 [0, i - 1] 位置内出现过，如果：dp[i - 1] < i - index ，此时说明字符 s[index] 在子字符串 dp[i - 1]区间之外，此时将 s[i]加入到以 s[i - 1]为结尾的最长不重复子串中，不会破坏规则，此时 dp[i] = dp[i - 1] + 1，比如说对于字符串 axxbcda 中，s[i] = 'a'，而前一个 ‘a’ 出现在dp[i - 1]的最长不重复子串之外，所以将 s[i] 加入到 s[i - 1]结尾的最长不重复子串中不会破坏规则。dp[i - 1] >= i - index，说明字符串 s[index]在子字符串 dp[i - 1] 的区间之内，所以此时以 s[i] 为结尾的最长不重复子串的长度由 s[index]中 index 的位置决定，即dp[i] = i - index。3、我们使用一个 Map 来保存字符 s[i] 的上一个出现位置，如果不存在，那么返回 -1 ，在循环过程中，需要更新这个 Map。3、解题代码public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) return 0; Map<Character, Integer> memo = new HashMap<>(); // 由于 dp[i] 只与前一个状态 dp[i - 1] 有关，所以使用一个变量进行滚动 int temp = 0, result = 0; for (int i = 0;i < s.length();i++) { // 如果没有对应的 key ，那么返回 -1 int index = memo.getOrDefault(s.charAt(i), -1); // 更新 map memo.put(s.charAt(i), i); temp = temp < i - index ? temp + 1 : i - index; result = Math.max(temp, result); } return result; }1.3、把数字翻译成字符串1、题目描述给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。示例一输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"2、解题思路使用动态规划解决这道题。明确 dp 数组的含义。我们设dp[i] 的含义为：下标范围为 [0, i] 的那部分数字有 dp[i] 种翻译方法。明确状态转移方程对于dp[i] 而言，我们需要进行分类讨论。1、当数字中的最后两个数字，即[i - 1, i] 范围的数字可以被翻译为一个数时，0 =< (i - 1) * 10 + i <= 25时，那么我们有两种选择，我们即可以直接将最后一个数字翻译为一个字母，此时存在等式 dp[i] = dp[i - 1] ；又可以将最后两个数字直接翻译成一个字母，此时存在等式 dp[i] = dp[i - 2]。情况 1 需要综合两个选择进行考虑，所以这种情况下 dp[i] = dp[i - 1] + dp[i - 2]。1、当数字中的最后两个数字无法直接被翻译为一个数时，此时我们别无选择，只有将最后一个数直接翻译成一个字母，此时存在等式dp[i] = dp[i - 1]。故我们可以得到以下的状态转移方程。if (最后两个数可以翻译为一个字母) { dp[i] = dp[i - 1] + dp[i - 2]; } else { dp[i] = dp[i - 1]; }数组初始化，对于第一个数字，我们只有将它直接转换为一个字母，此时 dp[0] = 1。3、解题代码 public int translateNum(int num) { //1 先将 num 转换为字符串 String str = String.valueOf(num); // 创建一个 dp 数组，长度为 str.length() int[] dp = new int[str.length()]; // 初始化 dp 数组 dp[0] = 1; // 从 1 开始 for (int i = 1;i < str.length();i++) { // 如果前一个数等于 1 ，或者前一个数等于 2 且当前数小于等于 5 if (str.charAt(i - 1) == '1' || (str.charAt(i - 1) == '2' && str.charAt(i) <= '5')) { if (i == 1) { // 如果 i == 1，那么直接初始化为 2 dp[i] = 2; } else { dp[i] = dp[i - 2] + dp[i - 1]; } } else { dp[i] = dp[i - 1]; } } return dp[str.length() - 1]; } 1.4、删除并获得点数1、题目描述给你一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i] ，删除它并获得nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1和nums[i] + 1的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。示例一输入：nums = [3,4,2] 输出：6 解释： 删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。示例二输入：nums = [2,2,3,3,3,4] 输出：9 解释： 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。2、解题思路这道题与打家劫舍的思路差不多，如果我们在原来数组的基础上构造一个新数组，这个数组以 元素的值为下标，nums[i] 表示 i 出现的次数，以示例二的数组为例，构造出来的新数组为：nums = {2,2,3,3,3,4} temp = {0,0,2,3,1}代表原来的数组中有 0 个 0 ，0 个 1 ，2 个 2 ，3 个 3 ，一个 4。这样就变成了打家劫舍问题。dp 数组的含义：其中 dp[i] 表示面对值为 i 的数时，能获得的最大点数为 dp[i]。状态转移方程和打家劫舍一样，我们在选择值为 i 的数时，不需要考虑 i + 1 的数，只需要考虑 i - 1 的情况，此时 dp[i] 有两个选择：1、第一个选择就是选择获取 i - 1 的点数，此时 i 的点数已经不能选择（因为 i 的值），所以此时有式子为 dp[i] = dp[i - 1]。2、第二个选择就是选择获取 i - 2的点数，此时可以选择 i 的点数，此时存在式子 dp[i] = dp[i - 2] + i * temp[i]。所以状态转移方程如下：dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * temp[i]);数组初始化和打家劫舍的 dp 数组初始化一样，但注意这里需要对构造出来的新数组进行初始化。3、解题代码public int deleteAndEarn(int[] nums) { if (nums == null || nums.length == 0) return 0; //1 先找出数组中的最大数，用于构造新数组 int max = Integer.MIN_VALUE; for (int num : nums) { max = Math.max(max, num); } if (max <= 0) return 0; // 必须是最大值 + 1 长度 int[] temp = new int[max + 1]; for (int num : nums) { temp[num]++; } // 接下来，就按照打家劫舍的方法做 if (temp.length == 1) return temp[0]; if (temp.length == 2) return Math.max(temp[0], temp[1]); int one = temp[0]; int two = Math.max(temp[0], temp[1]); int cur = 0; for (int i = 2;i < temp.length;i++) { cur = Math.max(two, one + i * temp[i]); one = two; two = cur; } return cur; }1.5、接雨水1、题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。2、解题思路dp 数组的含义，其中 dp[i] 表示在下标为 i 的柱子上可以装的水。我们设第 i 根柱子左边最高的柱子高度为 maxLeft， 同时记第 i 根柱子右边最高的柱子高度为 maxRight ，则第 i 根柱子上能承载的水量为：dp[i] = Math.max(0, Math.min(maxLeft, maxRight) - height[i])如果我们每次都需要向左右两边遍历找寻最大值，那么时间复杂度就会非常高。创建两个长度为 n 的数组 leftMax 和 rightMax ， 对于 0 <= i < n ，leftMax[i]表示下标 i 及其左边的位置中，height的最大高度；而 rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。1、leftMax[0] = height[0]， rightMax[n - 1] = height[n - 1]。2、当 1 <= i <= n - 1 时，leftMax[i] = Math.max(leftMax[i - 1], height[i])。3、当 0 <= i <= n - 2 时，rightMax[i] = Math.max(rightMax[i - 1], height[i])。因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。这道题中，我们不需要使用到 dp 数组，只需要使用一个变量进行保存同时累加即可。状态转移方程我们设在第 i 根柱子上能存的水为 count ，则：int count = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i])3、解题代码public int trap(int[] height) { if (height == null || height.length <= 2) return 0; int[] leftMax = new int[height.length]; leftMax[0] = height[0]; // 正向遍历，获取每根柱子左边的最大高度 for (int i = 1;i < height.length;i++) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } int[] rightMax = new int[height.length]; // 反向遍历，获取每根柱子右边的最大高度 rightMax[height.length - 1] = height[height.length - 1]; for (int i = height.length - 2;i >= 0;i--) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } // 使用一个变量来计算总水量 int sum = 0; // 第一根和最后一根柱子没有结果，直接跳过 for (int i = 1;i < height.length - 1;i++) { int count = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]); sum += count; } return sum; }1.6、丑数 II1、题目描述给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。（1 也可以看为一个丑数）。示例一输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。=丑数计算思路由于 1 也是丑数，那么我们可以将 1 作为基础乘以 2,3,5 ，得到的结果也是丑数，再将这些得到的结果分别乘以 2,3,5 ，得到的结果也都是丑数，然后按照从小到大取到第 n 个结果，就是第 n 个丑数：2、解题思路使用最小堆在这个解决思路中，我们需要创建一个小顶堆和一个集合，其中集合用于取出重复的丑数，比如说上图中生成的丑数存在相同的情况，我们需要进行去重。初始化时，最小堆中只存在丑数 1。循环遍历，将 1 从最小堆中取出，然后将 1 乘以三个质因子，然后将结果放入最小堆中（需要先到集合中看一下有没有这个元素，如果有那么就不加入到最小堆中）。不断从堆中取出元素，然后乘以质因子，再将没出现过的结果放入到最小堆中，循环 n 次，拿到的就是第 n 个丑数。动态规划1、dp 数组的含义：其中 dp[i] 表示第 i 个丑数的值，则第 n 个丑数即为 dp[n]。2、状态转移方程：定义三个指针 p2,p3,p5 ，表示下一个丑数是当前指针指向的丑数乘以对应的质因子。初始化时，三个指针的值均为 1 ，当 2 <= i <= n 时，有：dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3),dp[p5] * 5);然后我们需要比较 dp[i] 与 dp[p2] * 2 ，dp[p3] * 3 ，dp[p5] * 5 是否相等，如果相等则将对应的指针 + 1。从上面的图中，当求第二个丑数时，结果从 {2,3,5} 中 诞生，我们得到第二个丑数为 2 ，求第三个丑数时，我们在{3,5,4} 中求结果，可以看到 {3,5} 是上次求丑数留下来的结果，而 4 正是 2 * 2 ，即 1 后移（ + 1）后 * 2 的结果：3、dp 数组初始化：dp[1] 表示第一个丑数，初始化为 1。3、解题代码最小堆这里为了防止溢出，使用的是 Long 型。public int nthUglyNumber(int n) { if (n == 1) return 1; // 创建一个最小堆，用于存放丑数 PriorityQueue<Long> minHeap = new PriorityQueue<>(); // 创建一个数组，用于存放质因子。 int[] nums = {2, 3, 5}; Set<Long> set = new HashSet<>(); // 初始化，我们需要将 1 放入最小堆中 minHeap.add(1L); long result = 0; for (int i = 0;i < n;i++) { result = minHeap.poll(); for (int num : nums) { long uglyNum = num * result; // 只有集合中不存在时，才将结果加入到最小堆中 if (!set.contains(uglyNum)) { minHeap.add(uglyNum); set.add(uglyNum); } } } return (int)result; }动态规划public int nthUglyNumber(int n) { if (n == 1) return 1; int[] dp = new int[n + 1]; dp[1] = 1; int p2 = 1, p3 = 1, p5 = 1; for (int i = 2;i <= n;i++) { dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5); if (dp[i] == dp[p2] * 2) { p2++; } if (dp[i] == dp[p3] * 3) { p3++; } if (dp[i] == dp[p5] * 5) { p5++; } } return dp[n]; }1.7、跳跃游戏 I1、题目描述给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 2、解题思路dp 数组的含义：其中 dp[i] 表示能否到达下标为 i 的位置，所以 dp 应该是一个 boolean 类型的数组。状态转移方程。遍历 [0, i - 1] ，我们需要找到一个位置 j ，如果小人能到达 j 位置且满足条件 j + nums[j] >= i，那么证明 i 是可以到达的，此时我们可以使 dp[i] = true ，然后我们需要跳出循环。if(dp[j] && j + nums[j] > i) { dp[i] = true; }dp 数组的初始化：我们需要初始化 dp[0] = true，因为小人从 0 位置开始，同时需要返回 dp[nums.length - 1]。3、解题代码public boolean canJump(int[] nums) { if (nums == null || nums.length <= 1) return true; boolean[] dp = new boolean[nums.length]; dp[0] = true; for (int i = 1;i < nums.length;i++) { for (int j = 0;j < i;j++) { if (dp[j] && nums[j] + j >= i) { dp[i] = true; break; } } } return dp[nums.length - 1]; }1.8、跳跃游戏 II1、题目描述1、题目描述1、题目描述 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例一输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。2、解题思路dp 数组的含义其中 dp[i] 表示到达 i 位置所用的最小步数，我们需要返回 dp[nums.length - 1]。状态转移方程当我们处于第 i 个位置时，我们遍历 [0. i - 1] 位置，然后寻找在哪个位置可以直接用一步到达 i 位置。if (j + nums[j] >= i) { // 如果在 j 位置可以直接到达 i 位置，那么直接在到达 j 所需要的最少步数 dp[j] 的基础上 + 1即可，但我们需要和 dp[i] 做比较，取最小值 dp[i] = Math.min(dp[i], dp[j] + 1); }=初始化 dp 数组由于在状体转移方程中，我们需要使用 min 函数来选择最小值，那么我们给数组的初始化值就不能是简单的 0 ，为了方便，我们先将数组中的所有元素全部置为 Integer,MAX_VALUE。当 i 为 0 时，我们只需要 0 步就可以到达，所以 dp[0] = 0。当 i 为 1 时，我们只需要一步就可以到达，所以 dp[1] = 1。3、解题代码public int jump(int[] nums) { int len = nums.length; if (len <= 1) return 0; // 创建一个大小为 len 的数组，并对它的值进行初始化 int[] dp = new int[len]; // 初始化数组的值为 Integer.MAX_VALUE ，因为我们需要与 0 作比较取最小值，所以要初始化一个值 Arrays.fill(dp, Integer.MAX_VALUE); // 初始化 dp[0] 和 dp[1] ，当 i 等于 0 时，至少花 0 步就可以到达，当 i 等于 1 时，只需要一步就可以到达 1 dp[0] = 0; dp[1] = 1; for (int i = 2;i < len;i++) { for (int j = 0;j < i;j++) { // 如果在 [0, i - 1] 范围内有位置可以一步到达 i ，那么我们需要进行选择， if (j + nums[j] >= i) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[len - 1]; }1.9、环形子数组的最大和1、题目描述给定一个由整数数组 A 表示的**环形数组 C**，求 C 的非空子数组的最大可能和。 在此处，环形数组意味着数组的末端将会与开头相连呈环状。 （形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]） 此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。 （形式上，对于子数组 C[i], C[i+1], …, C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）示例一输入：[1,-2,3,-2] 输出：3 解释：从子数组 [3] 得到最大和 3示例二输入：[5,-3,5] 输出：10 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10示例三输入：[3,-1,2,-1] 输出：4 解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 42、解题思路1、对于一个环形数组来说，它的最大连续子数组其实只有两种情况：第一种，最大连续子数组分布在数组中间，比如说下面的情况：对于这种情况，我们只需要按照求普通数组的最大连续子数组的和的思路做即可。第二种，最大连续子数组首尾相连，比如说下面的情况：这种情况下，我们要求的值 answer 满足 answer = totalSum - min_so_far，其中 min_so_far表示图中灰色部分的和，即普通数组中最小连续子数组的和，我们可以借由最大连续子数组的和来做。3、解题代码public int maxSubarraySumCircular(int[] nums) { if (nums == null || nums.length == 0) return 0; int first = maxSubarray(nums); int total = 0; // 计算 total 的值 for (int num : nums) { total += num; } int min = minSubarray(nums); int second = total - min; // 如果 total 等于 min ，那么证明差为 0 ，那么此时如果 first 返回的值是负数，那么就会返回错误的 0 if (total == min) return first; return Math.max(first, second); } private int minSubarray(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int len = nums.length; int[] dp = new int[len]; dp[0] = nums[0]; int min = Integer.MAX_VALUE; for (int i = 1;i < len;i++) { dp[i] = Math.min(dp[i - 1] + nums[i], nums[i]); min = Math.min(dp[i], min); } return min; } private int maxSubarray(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int len = nums.length; int[] dp = new int[len]; int max = Integer.MIN_VALUE; dp[0] = nums[0]; for (int i = 1;i < len;i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); max = Math.max(dp[i], max); } return max; }2、乘积最大子数组1、题目描述给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）， 并返回该子数组所对应的乘积。示例一输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。示例二输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。2、解题思路与和最大子数组不一样的是，在本题中，我们需要根据当前遍历的元素来进行更新 dp 数组的值，我们设置两个变量，其中preMax 为 nums[0: i - 1]中最大的乘积，而preMin 为 nums[0: i - 1]中最小的乘积（可能为负数）。当 nums[i]为正数时，此时由于正正得正，我们需要更新 preMax = Math.max(preMax * nums[i], nums[i])，同时更新 preMin = Math.min(preMax * nums[i], nums[i])。当 nums[i]为负数时，此时由于负负为正得正，我们需要更新 preMax = Math.max(preMin * nums[i], nums[i])，同时更新 preMin = Math.min(preMin * nums[i], nums[i])。我们使用一个 max 变量来记录全局最大值，将其与 preMax 比较。3、解题代码public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; int preMax = nums[0], preMin = nums[0], max = nums[0]; int curMax = 0, curMin = 0; for (int i = 1;i < nums.length;i++) { if (nums[i] > 0) { curMax = preMax * nums[i]; curMin = preMin * nums[i]; } else { curMax = preMin * nums[i]; curMin = preMax * nums[i]; } preMax = Math.max(curMax, nums[i]); preMin = Math.min(curMin, nums[i]); max = Math.max(preMax, max); } return max; }2.1、乘积为正数的最长子数组长度1、题目描述给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组，请你返回乘积为正数的最长子数组长度。示例一输入：nums = [1,-2,-3,4] 输出：4 解释：数组本身乘积就是正数，值为 24 。示例二输入：nums = [-1,-2,-3,0,1] 输出：2 解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。2、解题思路与上一题相同，我们在遍历到某个元素时，根据这个元素的情况进行判断。确定 dp 数组的含义。我们需要创建两个数组，其中：1、pos[i] 表示以 i 结尾的乘积为正数的最长子数组长度。2、neg[i] 表示以 i 结尾的乘积为负数的最长子数组长度。状态转移方程1、当 nums[i] > 0 时，此时 nums[i] 的值不会影响之前子数组乘积的值的正负：所以，如果 pos[i - 1] 大于 0 ，那么此时它可以放心乘上 nums[i] ，如果 pos[i - 1] 等于 0 ， 那么子数组 {nums[i]} 就是以 i 结尾的乘积为正数的最长子数组，即此时 pos[i] = 1， 所以我们可以直接列出当 nums[i] 大于 0 的状态转移方程； 而如果 neg[i - 1] 大于 0 ，那么它也可以放心乘上 nums[i]，如果 neg[i - 1] 等于 0， 那么 neg[i ] 依然为 0。if (nums[i] > 0) { pos[i] = pos[i - 1] + 1; neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; }2、当 nums[i] < 0 时，此时 nums[i] 的值会影响之前子数组乘积的值的正负：如果 pos[i - 1] 大于 0，那么此时我们将 nums[i] 放入以 i - 1 结尾的子数组中， 整个子数组的乘积变为了负数，所以此时有 neg[i] = pos[i - 1] + 1；如果 pos[i - 1] 等于 0 ， 那么此时如果我们将 nums[i] 放入以 i - 1 结尾的子数组中，可能会导致整个子数组乘积变为正， 所以此时我们直接记 neg[i] 为 1 。 如果 neg[i - 1] 大于 0，那么此时将 nums[i] 放入以 i - 1 结尾的子数组中， 整个子数组的乘积变为了正数，所以此时 pos[i] 的值应该更新为 neg[i - 1] + 1 ， 如果 neg[i - 1] 的值等于 0 ，那么应该将 pos[i] 置为 0。 if (nums[i] < 0) { neg[i] = pos[i - 1] + 1; pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; }所以，我们可以得出状态转移方程如下：if (nums[i] > 0) { pos[i] = pos[i - 1] + 1; neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; } else if (nums[i] == 0) { pos[i] = neg[i] = 0; } else { neg[i] = pos[i - 1] + 1; pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; }dp 数组的初始化。这个需要根据 nums[0] 的值进行判断。1、当 nums[0] 大于 0 时， pos[0] = 1，neg[0] = 0。2、当 nums[0] 等于 0 时，直接初始化为 0。3、当 nums[0] 小于 0 时，neg[0] = 1，pos[i] = 0。3、解题代码public int getMaxLen(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0] > 0 ? 1 : 0; int[] pos = new int[nums.length]; int[] neg = new int[nums.length]; int max = Integer.MIN_VALUE; if (nums[0] > 0) { pos[0] = 1; } else if (nums[0] < 0) { neg[0] = 1; } for (int i = 1;i < nums.length;i++) { if (nums[i] > 0) { pos[i] = pos[i - 1] + 1; neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; } else if (nums[i] == 0) { pos[i] = 0; neg[i] = 0; } else { neg[i] = pos[i - 1] + 1; pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0; } max = Math.max(max, pos[i]); } return max; }由于在状态转移方程中， dp[i] 的值只与前一个状态相关，所以我们可以使用一个变量进行滚动更新：public int getMaxLen(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0] > 0 ? 1 : 0; int posMax = 0; int negMax = 0; int max = Integer.MIN_VALUE; if (nums[0] > 0) { posMax = 1; } else if (nums[0] < 0) { negMax = 1; } int curPos = 0; int curNeg = 0; for (int i = 1;i < nums.length;i++) { if (nums[i] > 0) { curPos = posMax + 1; curNeg = negMax > 0 ? negMax + 1 : 0; } else if (nums[i] == 0) { curPos = 0; curNeg = 0; } else { curNeg = posMax + 1; curPos = negMax > 0 ? negMax + 1 : 0; } // 进行滚动 negMax = curNeg; posMax = curPos; max = Math.max(max, curPos); } return max; }背包1.1、背包回顾1、题目描述有 N 件物品和一个最多能负重 W 的背包，其中第 i 件物品的重量是 weight[i]， 价值是 value[i]。每件物品只能使用一次，求解将哪些物品装入背包里， 得到的物品价值总和最大？2、使用动态规划求解明确选择和状态在这个问题中，状态包含两个变量，即背包的重量及所得到的价值，而选择也非常简单，就是是否选择将某件物品放入背包中。明确 dp 数组的含义，这里使用一个二维的 dp 数组来解决这个问题，其中 dp[i][j] 表示从下标 [0, i] 的物品中任意取，放入容量为 j 的背包中，所能获得价值的最大总和为多少明确递推公式1、对于第 i 件物品，当剩余背包容量无法容纳该物品，或者我们选择不将其放入到背包中时，此时有关系如下：dp[i][j] = dp[i - 1][j]2、对于第 i 件物品，当剩余背包容量可以容纳该物品，且我们选择将其放入到背包时，此时存在关系如下，其中 weight[i] 、 value[i ] 分别指 i 物品的重量与价值。dp[i][j] = dp[i - i][j - weight[i]] + value[i];因此我们可以得到以下的递推公式：if (j < weight[i]) { dp[i][j] = dp[i - 1][j] } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) }初始化 dp 数组1、当 j 为 0 时，此时背包容量为 0 ，因此可获取的最大价值也为 0 ，即 dp[i][0] = 0。2、当 i 为 0 时，即只有第一件物品可供选择时，如果此时背包容量 j >= weight[0] ，那么应该初始化对应的 dp[0][j] 为 value[0]。1.2、使用一维滚动数组优化背包问题1、优化思路当使用二维数组时，背包问题的递推公式为 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。可以看到，如果我们将 dp[i - 1] 那一层都拷贝到 dp[i] 上，那么表达式完全可以是 dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i]] + value[i])。当前层的状态完全由上一层状态推导而来，对于这种情况，我们可以考虑使用滚动数组进行优化，这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。2、含义介绍确定 dp 数组的含义在一维 dp 数组中， dp[j] 表示：容量为 j 的背包，所背的物品价值可以最大为 dp[j]。确定递推公式1、当我们选择不放物品 i 时，所得到的最大价值为 dp[j]，这里可以类比我们使用二维数组的时候，如果选择不放物品 i 时，我们得到的最大价值为 dp[i - 1][j] ， 等于是把 dp[i][j] 的上一层数据拷贝下来。2、当我们选择放物品 i 时，所得到的最大价值为 dp[j - weight[i]] + value[i]。所以，我们可以得到使用一维数组时，01 背包问题的递推公式为：if (j < weight[i]) { dp[j] = dp[j]; } else { dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); }dp 数组初始化当 j 为 0 时，此时背包容量为 0 ，所以所能装的物品的最大价值也是 0 ，即 dp[0] = 0； 对于其他位置的值，我们同样将其初始化为 0 ， 避免因初始化值过大导致递推公式计算出来的值无法将初始值覆盖（将整个数组都初始化为 0 。 遍历顺序在二维数组中，无论是先遍历物品，还是先遍历背包都是可以的， 但是在一维 dp 数组中，我们需要先遍历物品，然后再遍历背包， 同时需要注意的是，我们在遍历背包时，需要进行倒序遍历。 为什么要倒序遍历背包？这是为了保证物品只被添加一次，在使用二维数组时， 当前层和上一层的数据是完全隔离开的，所以正序遍历和倒序遍历都可以， 但当我们使用一维数组时， 如果先计算 dp[j - 1] ，那么它可能会影响到后面 dp [j] 的数据， 我们可以来举一个例子，其中 weight = {1,3,4} ，values = {15,20,30} ，同时最大容量 capacity = 4。 1、当我们使用正序遍历时， dp[1] = Math.max(dp[1], dp[1 - weight[0]] + values[0]) = Math.max(dp[1], dp[1 - 1] + 15) = 15; dp[2] = Math.max(dp[2], dp[2 - weight[0]] + values[0]) = Math.max(dp[2], dp[2 - 1] + 15) = 30。可以看到，如果我们使用正序遍历，那么在计算 dp[2] 时，递推公式中的 dp[2 - 1] = dp[1]是我们在上一次计算出来的 15 ，而且得到的结果也是 30 ，这相当于我们将第 0 件物品重复加入到了背包中。1、当我们使用倒序遍历时， dp[2] = max(dp[2], dp[2 - weight[0]] + values[0]) = max (0, dp[1] + 15) = 15；dp[1] = max(dp[1], dp[1 - weight[0]] + values[0]) = max(0, dp[0] + 15) = 15。此时可以看到，第 0 件物品只被加入到了一次，这是因为此时在计算 dp[j] 时， dp[j - 1]的结果还没有被计算出来，所以不会影响 dp[j]的计算。3、解题代码public static int knapsack(int number, int capacity, int[] weight, int[] values) { if (weight == null || values == null || weight.length != values.length) return 0; // 创建一个一维的 dp 数组，dp[j] 表示，当背包容量为 j 时，该背包能容纳物品的最大价值 int[] dp = new int[capacity + 1]; // 外层循环，先遍历物品 for (int i = 0;i < number;i++) { // 内层循环，需要倒序遍历背包 for (int j = capacity;j >= weight[i];j--) { // 使用递推公式，从右至左计算 dp[j] 的值 dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); } } // 最后返回 dp[capacity] ，就是 capacity 容量的背包所能容纳的物品的最大价值 return dp[capacity]; }1.3、目标和1、题目描述给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。示例一输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3示例二输入：nums = [1], target = 1 输出：12、解题思路使用动态规划来解决这道题，这道题也可以转换为 01 背包问题，与 01 背包问题不同的是，前者可以选择是否将这件物品装入背包中，而本题要求全部数字都被选中，但可以选择+ 和-。将这个数组分割为两部分，其中被赋予 + 的那一部分称为 P ，而被赋予 - 的那一部分称为N，所以我们可以得到以下结论。1、sum(P) - sum(N) = S。2、sum(P) + sum(N)= 数组中所有元素的和 sum。3、将上面的式子相加，有 2 * sum(P) = target + sum，移项有 sum(P) = (target + sum) / 2，我们记这个值为 result，即 result = (target + sum) / 2。所以问题就转换为求容量为 result 的 01 背包问题，要装满容量为 result 的背包，有几种方案：如果 target 的值大于 sum ，那么直接返回 0 ，因为此时无法找到一种可能的实现。如果 sum§ 不是正数，即 (target + sum) 不是偶数，那么返回 0。确定 dp 数组的含义dp[j] 表示在数据 nums 中，凑出 j 的方法有 dp[j] 种，换成背包问题就是，如果要填充 j 这么大容积的包，有 dp[j] 种方法。确定递推公式1、填满容量为 j - nums[i] 的背包，有 dp[j - nums[i]] 种方法。2、那么只需要获得 nums[i] ，我们就可以凑出 dp[j] ，此时得到 dp[j] 的方法有 dp[j - nums[i]] ，这里有点类似凑硬币。比如说，如果我们当前需要计算 dp[5] ，同时我们手中有一个重量为2的物品，此时我们只需要计算出 dp[3] 就可以得到在我们有 重量为 2的物品的前提下，能填满容量为5的背包的方法，所以我们可以得到以下的递推公式。dp[j] += dp[j - nums[i]]1初始化 dp 数组这道题中，由于我们要求 dp[result] ，所以我们需要初始化一个长度为result + 1 的数组，同时，当 j == 0 时，使用 nums 数组中的元素可以有一种方法凑出 0 ，故 dp[0] = 1 ;3、解题代码这里使用一维滚动数组来解这道题。public int findTargetSumWays(int[] nums, int target) { if (nums == null || nums.length == 0) return 0; //1 计算数组元素和 int sum = gengerateSumByArray(nums); //2 如果 sum 小于 target 或者 （sum + target） 不是偶数，那么直接返回 0 if (sum < target || (sum + target) % 2 == 1) return 0; //3 使用一个变量保存 (sum + target) / 2; target = (sum + target) / 2; //这里需要进行判断，如果计算出来的 target 小于 0 ，那么需要将其变为相反数 target = Math.abs(target); //4 创建一个长度为 target + 1 的数组，并进行初始化 int[] dp = new int[target + 1]; // 当 j == 0 时，此时在 nums 中，只能找出一种方案凑出 0 ，所以 dp[0] = 1 dp[0] = 1; //5 外层循环遍历物品 for (int num : nums) { //6 内层循环倒序遍历背包 for (int j = target;j >= num;j--) { // 使用递推公式累加 dp[j] 的值 dp[j] += dp[j - num]; } } return dp[target]; } private int gengerateSumByArray(int[] nums) { int sum = 0; for (int num: nums) sum += num; return sum; }1.4、使用一维滚动数组优化分割等和子集问题1、优化思路使用一维滚动数组代替原来的二维数组dp 数组的含义dp 是一个一维的 boolean 数组，其中 dp[j] 表示在数组中，是否可以找到一个子集，使得这些子集的和等于 j。递推公式当我们知道数组元素 nums[i] 时，此时如果 dp[j] 或 dp[j - nums[i]] 有一个为 true ，那么就代表 dp[j] 为 true ，即：dp[j] = dp[j] || dp[j - nums[i]]2、解题代码/** * 这道题可以看为，在 nums 中，是否可以找到几个数，这几个数的和为 sum / 2 ，其中 sum 为数组元素和 */ public boolean canPartition(int[] nums) { if (nums == null || nums.length == 0) return true; //1 计算数组元素和 int sum = gengerateSumByArray(nums); // 如果数组元素和不是一个偶数，那么直接返回 false if (sum % 2 != 0) return false; int target = sum / 2; //2 我们需要在数组 nums 中，找到是否存在几个数字，满足这几个数字的和为 target // dp[j] 表示在数组 nums 中，是否存在几个数字，满足这几个数字的和为 j boolean[] dp = new boolean[target + 1]; // 初始化 dp 数组，当 j == 0 时，此时可以找到几个数字，满足这几个数字的和为 0 dp[0] = true; for (int num : nums) { for (int j = target;j >= num;j--) { // 如果 dp[j] 或 dp[j - num] 有一个为真，那么 dp[j] 即为真，此时代表存在... dp[j] = dp[j] || dp[j - num]; } } return dp[target]; } private int gengerateSumByArray(int[] nums) { int sum = 0; for (int num : nums) sum += num; return sum; }1.5、最后一块石头的重量 II1、解题思路在上面有提到，这道题其实就是尽量将石头分成重量相同的两堆，然后让相撞之后剩下的石头最小。 这道题其实就是求，给你一个大小为 sum / 2 的背包，其中 sum 为 nums 的元素和， 然后尽可能地往背包中装东西，我们假设最多往背包中装了 maxWeight 重量的石头， 那么我们要求的结果就是 sum - 2 * maxWeight;确定 dp 数组使用一个一维的 boolean 类型的 dp 数组， 其中 dp[j] 的含义、状态转移方程与 分割等和子集 问题中 dp 数组的含义相同，即在数组 nums 中， 能否找到一个子集，使得这个子集的元素和的值等于 j 。 当计算好 dp 数组后，我们需要反向遍历 dp 数组，寻找第一个为 true 的元素值，然后得到结果并返回，结果为 sum - 2 * j。2、解题代码public int lastStoneWeightII(int[] stones) { if (stones == null || stones.length == 0) return 0; int sum = generateSumByArray(stones); // 计算出 target 的值，我们要尽可能装满这个容量为 target 的包 int target = sum / 2; boolean[] dp = new boolean[target + 1]; dp[0] = true; // 外层循环遍历物品 for (int stone : stones) { // 内层循环反向遍历背包 for (int j = target;j >= stone;j--) { dp[j] = dp[j] || dp[j - stone]; } } // 填完表后，我们需要找到最接近 target 的一个 j 值 for (int j = target;;j--) { // 找到第一个为 true 的j if (dp[j]) { return sum - 2 * j; } } } private int generateSumByArray(int[] stones) { int sum = 0; for (int stone : stones) sum += stone; return sum; }1.6、一和零1、题目描述给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。示例 一输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。示例 二输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。2、解题思路这道题也可以看为 01 背包问题，其中字符串数组中的每一个字符串都是一件物品，而 m 和 n 相当于一个二维的背包。确定 dp 数组的含义，这里使用滚动数组进行优化，其中 dp[i][j]表示最多有 i 个 0 和 j 个 1 的 strs 的最大子集的大小为 dp[i][j]。对于 dp[i][j]而言，它可以由前一个 strs 里的字符串推导出来，假设该字符串中含有 zeroNum 个 0 ，同时含有 oneNum个 1 ，那么有以下的递推公式。dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)如何初始化 dp 数组？只需要将 dp 初始化为 0 即可:3、解题代码public int findMaxForm(String[] strs, int m, int n) { if (strs == null || strs.length == 0) return 0; // 创建一个二维数组，其中 dp[i][j] 表示子集最多能有 i 个 0 ，j 个 1 时，最大子集的长度 int[][] dp = new int[m + 1][n + 1]; // 外层循环遍历物品，在这道题中，一个字符串就是一件物品 for (String str : strs) { // 获取这个字符串中 1 的个数和 0 的个数 int zeroNum = countCharNum(str, '0'); int oneNum = countCharNum(str, '1'); // 内层循环遍历背包，这里有两个背包需要进行遍历，分别为容量为 m 的背包和 容量为 n 的背包，倒序遍历 for (int i = m;i >= zeroNum;i--) { for (int j = n;j >= oneNum;j--) { // 使用递推公式计算 dp[i][j] 的值 dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); } } } return dp[m][n]; } private int countCharNum(String str, char ch) { int num = 0; for (int i = 0;i < str.length();i++) { if (str.charAt(i) == ch) { num++; } } return num; }完全背包问题1.1、完全背包问题理论说明1、题目描述设有 n 种物品，每种物品都有一个重量及一个价值，其中第 i 件物品的重量为 weight[i]，价值为 value[i]。且每种物品的数量是无限的，同时有一个背包，最大载重量为M ，今从 n 种物品种选取若干个物品（同一种物品可以被多次选取）放入背包中，使其重量的和小于等于 M ，而价值的和为最大。与 01 背包不同的是，前者每件物品只有一个，而完全背包问题中每种物品可以有无限多个。2、解题思路在完全背包问题中，对于第 i 件物品，我们有几种选择：1、选择将 0 个物品装入到背包中。2、选择将 n 个该物品装入到背包中，我们可以不断往背包中添加该物品，直到背包被装满，也就是说，在完全背包问题中，同一件物品被装入背包的次数是有上下限的，下限为 0 ，上限为 M / n （向下取整）。当前背包容量为 j 时，对于第 i 件物品装入背包的次数范围为 [0, j / w[i]] ，其中 j / w[i] 需要向下取整。在之前使用一维滚动数组优化 01 背包问题时，我们有谈及到为什么内层循环需要进行反向遍历 – 为了避免一个物品被重复添加到背包中多次；而完全背包问题里的物品完全可以多次添加到背包中，所以对于完全背包问题的内层循环，我们可以正序遍历背包。3、解题代码/** * 求解完全背包问题 * @param number 物品个数 * @param capacity 背包容量 * @param weight 物品重量数组 * @param value 物品价值数组 * @return 能获取到的最大收益 */ public int completeBackpack(int number, int capacity, int[] weight, int[] value) { if (weight == null || value == null || weight.length != value.length) { return 0; } // 创建一个一维数组 dp int[] dp = new int[capacity + 1]; // 外层数组遍历物品 for (int i = 0;i < number;i++) { // 内层物品遍历背包，这里需要从左往右遍历 for (int j = weight[i];j <= capacity;j++) { // 使用递推公式 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } return dp[capacity]; }1.2、零钱兑换1、题目描述给你一个整数数组 `coins` ，表示不同面额的硬币；以及一个整数 `amount` ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 ， 你可以认为每种硬币的数量是无限的。示例一输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1示例二输入：coins = [2], amount = 3 输出：-12、解题思路这个问题可以看为一个完全背包问题，在这道题中，我们需要求解最值问题。确定 dp 数组含义。其中 dp[j] 表示，要想在 coins 中凑出金额为 j 的零钱，最少需要 dp[j] 个硬币。状态转移方程如果我们手一个 coins[i] ，那么我们只需要计算出凑出 j - coins[i] 的最少硬币数，然后 + 1，即可得到凑出 j 的最少硬币数，所以，我们得到的状态转移方程如下：dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1); // 注意，这里需要当子问题有解时才进行状态转移，即 dp[j - coins[i]] 不为 Integer.MAX_VALUE 时初始化 dp 数组1、当 j 为 0 时，此时只需要 0 个硬币就可以凑出，所以 dp[0] = 0;2、当 j 不为 0 时，我们需要将其初始化为一个非常大的数，避免后面在求出一个大于 0 的数时，在经由 Math.min (0, dp[j]) 进行选择时，让 0 覆盖了结果值，比如说，我现在求出了 dp[1] 为 1 ，但是我的 dp[1] 在初始化时初始化为 0 了，所以导致我在进行取最小值时，无法将 dp[1] = 1 这个值正确地更新到数组中。什么样的子问题才需要进行求解？在我们进行遍历时，只有当子问题有解时，我们才考虑进行递推，所以，如果 dp[j - coin] 的值为 Integer.MAX_VALUE ，那么我们没必要进行状态转移，因为此时代表这个问题无解。3、解题代码public int coinChange(int[] coins, int amount) { if (coins == null || coins.length == 0) return -1; if (amount == 0) return 0; // 创建一个 dp 数组，长度为 amount + 1 ，其中 dp[amount] 就是在 coins 数组中，凑出 amount 所需的最少硬币数，也就是我们要求的结果 int[] dp = new int[amount + 1]; // 初始化 dp 数组，dp[0] = 1，这一步可以省略，我们需要将 dp 数组中非 0 位置的元素 初始化为 Integer.MAX_VALUE for (int i = 1;i < dp.length;i++) { dp[i] = Integer.MAX_VALUE; } // 外层遍历，遍历物品，也即硬币 for (int coin : coins) { // 内层遍历，正向遍历背包， for (int j = coin;j <= amount;j++) { // dp[j - coin] 不为 Integer.MAX_VALUE 时，证明此时 j - coin 可以被凑出，即这个问题有解，此时才需要进行求解。 if (dp[j - coin] != Integer.MAX_VALUE) { // 使用状态转移方程求解 dp[j] 的值，这里求得是最小值 dp[j] = Math.min(dp[j], dp[j - coin] + 1); } } } return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount]; }1.3、零钱兑换 II1、题目描述给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 ，假设每一种面额的硬币有无限个。示例一输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1示例二输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。2、解题思路使用动态规划解决这道题，在本题中，由于每一种面额的硬币有无限个，我们将给定的 coins 数组看为物品数组，coins 数组中每个硬币的数额看为物品的重量，我们要做的就是寻找出凑齐 amount 重量的背包的方案数，这是一个完全背包问题。确定 dp 数组的含义dp[j] 指的是，在 coins 数组中，有 dp[j] 种凑出 amount 数值的方案。状态转移方程这是典型的组合问题，当我们手上有一颗数值为 coins[i] 的硬币时，此时我们只需要知道在 coins 中凑出 amount - nums[i] 的方案数，就可以得到该条件下的方案数，所以状态转移方程应该如下：dp[j] += dp[j - nums[i]]初始化 dp 数组，当 j 为 0 时，此时有一种方案可以凑出 0 ，所以：dp[0] = 1;3、解题代码public int change(int amount, int[] coins) { if (coins == null || coins.length == 0) return 0; // 创建一个 dp 数组，其中 dp[j] 表示在 coins 中，能凑出数额为 j 的方案数 int[] dp = new int[amount + 1]; // 初始化 dp 数组，当 j 为 0 时， dp[j] == 1 dp[0] = 1; // 外层遍历，遍历物品 for (int i = 0;i < coins.length;i++) { // 内层遍历，对于完全背包问题，我们需要正向遍历背包 for (int j = coins[i];j <= amount;j++) { // 使用递推公式计算出 dp[j] dp[j] += dp[j - coins[i]]; } } return dp[amount]; }1.4、组合总和 IV1、题目描述给你一个由 不同 整数组成的数组 `nums` ，和一个目标整数 `target` 。 请你从 `nums` 中找出并返回总和为 `target` 的元素组合的个数。 请注意，顺序不同的序列被视作不同的组合。示例 一输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。示例 二输入：nums = [9], target = 3 输出：02、解题思路这道题是典型的完全背包问题，同时求的是排列数，所以外层循环需要遍历背包，内层循环需要遍历物品。确定 dp 数组的含义。dp[i] 表示凑成正整数为 i 的排列个数为 dp[i]。确定递推公式dp[i] 可以由 dp[i - nums[j]] 推导出来，其中dp[i] 考虑了 nums[j] ，而dp[i - nums[j]]不考虑 nums[j]，因为只要得到 nums[j]，排列个数 dp[i - nums[j]]，就是 dp[i]的一部分。我们可以确定递推公式如下：dp[i] += dp[i - nums[j]];初始化 dp 数组由于递推公式为 dp[i] += dp[i - nums[j]] 的缘故，所以 dp[0] 要初始化为 1 ，这样递归其他 dp[i] 时才会有数值基础。这里需要注意， dp[0] 是没有意义的。3、解题代码 public int combinationSum4(int[] nums, int target) { if (nums == null || nums.length == 0) return 0; // 创建一个 dp 数组，其中 dp[i] 表示能在 nums 中能组成 i 的排列数 int[] dp = new int[target + 1]; // 初始化 dp[0] = 1 ，这个 dp[0] 是没有含义的 dp[0] = 1; // 外层循环遍历背包 for (int i = 0;i <= target;i++) { // 内层循环遍历物品 for (int j = 0;j < nums.length;j++) { // 只有当背包容量大于第 j 件物品时，才需要进行分割子问题 if (i >= nums[j]) { dp[i] += dp[i - nums[j]]; } } } return dp[target]; }1.5、爬楼梯1、题目描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例一输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例二输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶2、解题思路使用完全背包的思路解决这道题，这道题又是一道排列数的问题。此时，背包中只有两件物品，即 1 和 2 ，我们需要找出装满容量为 n 的背包的方案数。确定 dp 数组的含义。其中 dp[i] 表示爬上 n 阶楼梯有 dp[i] 种不同的排列方案。确定递推公式由于此时球的是排列方法，所以我们可以得到本体的递推公式：dp[i] += dp[i - nums[j]];初始化 dp 数组与上题相同，由于此时递推公式是 dp[i] += dp[i - nums[j]] ，所以我们需要初始 dp[0] = 1 ，这是递推的基础值。本题中的物品在本题中，只有两个物品，其中第一个物品的重量为 1 ，第二个物品的重量为 2。3、解题代码public int climbStairs(int n) { if (n == 1 || n == 2) return n; // 初始化一个 dp 数组，长度为 n + 1，其中 dp[i] 表示爬上 i 阶楼梯的方案排列数 int[] dp = new int[n + 1]; // 初始化 dp 数组 dp[0] = 1; // 外层循环，在求排列的过程中需要遍历背包 for (int i = 0;i <= n;i++) { // 内层循环，需要遍历物品，这里只有两件物品，其中第一件物品的重量为 1 ，第二件物品的重量为 2 for (int j = 1;j <= 2;j++) { // 如果当前背包的容量大于物品重量，这里为 j if (i >= j) { dp[i] += dp[i - j]; } } } return dp[n]; }1.6、完全平方数1、题目描述给定正整数 n ，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n 。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。示例一输入：n = 12 输出：3 解释：12 = 4 + 4 + 4示例二输入：n = 13 输出：2 解释：13 = 4 + 92、解题思路这道题中，n 可以有多个相同的完全平方数 x^2 组成，也就是说，如果我们将 x 看为背包问题中的物品，那么每个 x 可以被多次加入到背包中。我们可以将这道题转换为，给你一个容量为 n 的背包，同时给你一些物品，而物品由 n 决定，物品为 [1, b] ，其中满足 b * b <= n 且 (b + 1) * (b + 1) > n。明确 dp 数组含义。其中 dp[j] 表示 j 最少可以由 dp[j] 个完全平方数组成。确定状态转移方程，这道题是一道求最值问题，所以状态转移方程为：dp[j] = Math.min(dp[j], dp[j - i * i] + 1);当我们手中握有 i * i 这个平方数时，我们只需要求出组成 j - i * i 最少需要多少个平方数，然后再这个结果的基础上加上一，就得到了我们想要的结果。初始化 dp 数组1、dp[0] 可以由 0 个平方数组成，所以 dp[0] = 0。2、dp[1] 可以由一个平方数组成，所以dp[1] = 1。3、对于其他下标的元素，在使用递推公式进行运算时，我们不希望它的真正结果被 0 覆盖，所以我们将其他下标的值都初始化为 Integer.MAX_VALUE。在进行子问题分割时，只有当 dp[j - i * i] 不为 Integer.MAX_VALUE 时（此时子问题存在有效解），才进行递推公式的计算。3、解题代码private int getSizeByN(int n) { int size = 0; // 比如说 size 为 10 ，那么比 10 小的平方数有 1、4和9，可供选择的物品有 1 2 3 while (true) { // 如果 size + 1 的平方大于 n ，那么此时直接 break ，得到的 size 就是我们要寻找的值，当前物品的个数就是 1 - n if ((size + 1) * (size + 1) > n) { break; } size++; } return size; }使用两个循环来解决这道题，先遍历物品后遍历背包，只有当当前背包容量大于 i * i 且子问题有效时，才能进行状态转移。public int numSquares(int n) { if (n == 1) return 1; // 创建一个 dp 数组，其中 dp[i] 表示和为 i 的完全平方数的最少数量 int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); // 初始化 dp 数组 dp[0] = 0; // 计算出当前物品的个数，即 size int size = getSizeByN(n); // 外层循环遍历物品 for (int i = 1;i <= size;i++) { // 内层循环正序遍历背包，只有当当前背包容量大于等于物品重量的平方时且子问题有解时，才能进行状态转移 for (int j = 0;j <= n;j++) { if (j >= i * i && dp[j - i * i] != Integer.MAX_VALUE) { // 此时可以进行状态转移 dp[j] = Math.min(dp[j], dp[j - i * i] + 1); } } } return dp[n]; }背包问题总结背包问题大体的接替模板是两层循环，分别是外层循环遍历物品，然后内层循环遍历背包，然后在循环中写状态转移方程。在我现在的学习中，背包问题可以根据所给条件和待求项分为以下几类：1.1、根据所给条件分类根据所给物品的个数，可以分为 01 背包问题和完全背包问题，在使用一维数组进行空间优化时，二者的区别是内层循环的遍历顺序，其中：对于 01 背包问题而言，内层循环在遍历背包时需要逆序遍历，保证物品只被加入到背包中一次。对于完全背包问题而言，内层循环在遍历背包时需要正序遍历。1.2、根据待求项分类1、最值问题 I问背包最多能装多少，状态转移方程一般如下：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);**2、存在问题**当我们求解存在问题时，状态转移方程一般如下：dp[j] = dp[j] || dp[j - nums[i]];比如说上面我们就是将 分割等和子集 、 最后一块石头重量 II 看为存在问题解决。3、组合问题当我们求解存在问题时，状态转移方程一般如下：dp[j] += dp[j - nums[i]];比如说上面提到的零钱兑换 II 、 目标和 就是这类问题。4、最值问题 II问装满背包所有物品的最小个数，状态转移方程一般如下：dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);零钱问题 I 就是这样的问题。1.3、组合问题和排列问题1、组合问题组合数的概念：从 n 个不同元素中，任取 m（m≤n）个元素不计顺序的组成一组，则所有不同的组合个数，称为组合数。如果求组合数，那么就是外层循环遍历物品，内层循环遍历背包。2、排列问题排列数的概念：从 n 个不同元素中，任取 m（m≤n）个元素有顺序的排成一列，则所有不同的排列个数，称为排列数。如果求组合数，那么就是外层循环遍历背包，内层循环遍历物品。编辑距离问题总结在使用动态规划求解字符串相关问题时， dp[i][j] 的含义通常是指字符串 s1 下标范围为 [0. i - 1] 的子串 a ，与字符串 s2 下标范围为 [0, j - 1] 的子串 b ，二者之间的某些指标。个人觉得是为了考虑空串，同时为了 初始化工作的方便。1.1、判断子序列dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为[0, i - 1] 的子串 a ，是否为字符串 t 中范围下标为[0, j - 1]的字符串 b 的子序列， dp 数组是一个二维的boolean 数组。当s[i - 1] == t[j - 1]时，此时表示 s 与 t 找到了一个公共字符，此时我们只需要判断当前 s 的子串 a ，在去掉公共字符后，是否为去掉公共字符的 b 的子序列即可（其中 b 为 t 的子串）。此时 s[0, i - 1] 是否为 t[0, j - 1]的子序列，这个结果完全由 s[0, i - 2] 与 t[0, j - 2]的关系决定。如果此时 a 是 b 的子序列，那么证明s[0, i - 1] 是 t[0, j - 1]的子序列；反之则不是。当s[i - 1] != t[j - 1]，此时我们需要删去 t 子串中的最后一个字符 t[j - 1] ，因为此时 s[0, i - 1] 是否为 t[0,j - 1]的子序列与t[j - 1]完全没有关系。如果 s[0, i - 1] 已经是 t[0, j - 2] 的子序列，那么 s[0, i - 1] 也必定为 t[0, j - 1] 的子序列。如果 s[0, i - 1] 已经是 t[0, j - 2] 的子序列，那么 s[0, i - 1] 也必定为 t[0, j - 1] 的子序列。 如果 s[0, i - 1] 并不是 t[0, j - 2] 的子序列， 那么此时 t[j - 1] 这个字符于事无补，所以 s[0, i - 1] 也一定不为 t[0, j - 1] 的子序列。本题递推公式if (s[i - 1] == t[i - 1]) { dp[i][j] = dp[i - 1][j - 1] } else { dp[i][j] = dp[i][j - 1] }1.2、不同的子序列dp 数组含义：dp[i][j]表示字符串 s 中范围下标为[0, i - 1]的子串 a ，在字符串 t 中范围下标为[0, j - 1]的字符串 b 中作为子序列出现的次数，dp 数组是一个二维的 int 数组。当 s[i - 1] == t[j - 1] 时，此时出现了公共字符，那么我们有两个选择：1、第一个选择就是让 s[i - 1] 字符直接与 t[j - 1]进行匹配，比如说 s = bag , t = baagg，我们可以选择让 t 中的最后一个 g 与 s 的最后一个 g 进行匹配，这是其中一种选择，这种选择下得到的个数为dp[i][j] = dp[i - 1][j - 1] ，即我们只需要查找 s[0, i - 2]在t[0,j - 1] 中作为子序列出现的次数即可。2、第二种选择就是让 s[i - 2]字符与 t[j - 1]进行匹配，而 s[i - 1]不参与匹配，比如说s = bag,t = baagg ，让 t 中倒数第二个 g 与 s 中的最后一个 g 进行匹配，这也是其中一种情况，这种情况下得到的个数为 dp[i][j] = dp[i][j - 1]，我们需要查找 s[0. i - 1] 在t[0, j - 2]中作为子序列出现的次数。由于本题中我们需要求出所有情况下出现次数之和，所以我们需要将上面两种选择得到的结果进行汇总。当 s[i - 1] != t[j - 1] 时，此时我们只能舍弃 t 中最后一个字符，然后用剩下的字符进行匹配，此时式子为 dp[i][j] = dp[i][j - 1]。递推公式if (s[i - 1] == t[i - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + 2); }1.3、两个字符串中的删除操作dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为 [0, i - 1]的子串 a ，变为字符串 t 中范围下标为 [0, j - 1]的子串 b ，所需要进行的删除操作次数。当 s[i - 1] == t[j - 1]时，此时我们此刻相等的字符为公共字符，从a[0, i - 1] 变为 b[0, j - 1]所需的最小删除次数与a[0, i - 2]变为b[0. j - 1]所需的最小删除次数相等，也就是说，公共字符的存在与否并不会对两个字符串的最小删除次数造成影响，所以我们可以得出此时的式子为 dp[i][j] = dp[i - 1][j - 1]。当s[i - 1] == t[j - 1]时，此时我们用三种做法可供选择，此时我们假设 s 的子串为 a ，t 的子串为 b。1、删去 a 中的某一个字符，此时得到的式子为 dp[i - 1][j] + 1，1 表示删去 a 中字符的那一次操作。2、删去 b 中的某一个字符，此时得到的式子为 dp[i][j - 1] + 1 ，1 表示删去 b 中字符的那一次操作。3、同时删去 a 和 b 中的字符，此时得到的式子为 dp[i - 1][j - 1] + 2。由于我们要求最小删除次数，所以我们需要在上述的三种情况中选择一个最小的结果。递推公式if (s[i - 1] == t[i - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; }1.4、编辑距离dp 数组含义：dp[i][j] 表示字符串 s 中范围下标为 [0, i - 1] 的子串 a ，与字符串 t 中范围下标为 [0, j - 1] 的子串 b 之间的最小编辑距离。当 s[i - 1] == t[j - 1] 时，此时子串 a 和 子串 b 二者的编辑距离与去掉公共字符的编辑距离相等，即 dp[i][j] = dp[i - 1][j - 1]。当 s[i - 1] == t[j - 1] 时，此时我们有几种做法可供选择：1、word1 删除一个元素，那么就是以下标 word1[0, i - 2] 与 word2[0, j - 1]的最短编辑距离，再加上一个删除操作，此时得到的式子应该为 dp[i - 1][j] + 1。2、word2 删除一个元素，那么就是以下标 word1[0, i - 1] 与 word2[0. j - 2] 的最短编辑距离，再加上一个删除操作，此时得到的式子应该为dp[i][j - 1] + 1。3、替换元素，此时 word1 替换 word1[i - 1] ，使其等于 word2[j - 1] ，此时我们又可以将 word1[i - 1]看为一个公共元素，只不过我们需要原来的基础上加上一次编辑，此时得到的式子为 dp[i - 1][j - 1] + 1。4、对于添加操作来说， word1 添加一个字符，就相当于 word2 删除一个字符，比如说，当 word1 为 abce ，word2 为 abc 时，word1 删去 e 与 word2 加上 e 的结果都相同，所以我们只需要考虑删除的情况即可。递推公式if (s[i - 1] == t[i - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; }

1 简介Distortion is often considered as an unfavorable factor in most image analysis. However, it is undeniable that the distortion reflects the intrinsic property of the lens, especially, the extreme wide-angle lens, which has a significant distortion. In this paper, we discuss how explicitly employing the distortion cues can detect the forgery object in distortion image and make the following contributions: 1) a radial distortion projection model is adopted to simplify the traditional captured ray-based models, where the straight world line is projected into a great circle on the viewing sphere; 2) two bottom-up cues based on distortion constraint are provided to discriminate the authentication of the line in the image; 3) a fake saliency map is used to maximum fake detection density, and based on the fake saliency map, an energy function is provided to achieve the pixel-level forgery object via graph cut. Experimental results on simulated data and real images demonstrate the performances of our method.2 部分代码% Demo for "Forgery Authentication in Extreme Wide-angle Lens Using Distortion Cue and Fake Saliency Map" close all; clear; clc;% Read datasavefile = 'ForensicImage/PSTest-5';orgimage = imread(strcat(savefile,'.jpg'));load(strcat(savefile,'.mat'));figure,subplot(131);imshow(orgimage);title('Forgery image');% compute the measure cueK_value=line_number:4;fake_saliency=zeros(size(orgimage,1),size(orgimage,2),'uint8'); Grave_Point_x=0;Grave_Point_y=0;Grave_K=0;for i=1:line_number % the distance cue K_value(i,1)=Distance_inv(Points(((1+(i-1)*3):(3+(i-1)*3)),:),fish_x,fish_y,fish_r,1); % the volume cue K_value(i,2)=Volume_inv(Points(((1+(i-1)*3):(3+(i-1)*3)),:),fish_x,fish_y,fish_r,1); % the combine cue K_value(i,3)=Combine(K_value(i,2),K_value(i,1)); % the untrustworthy likelihood K_value(i,4)=1-0.9*exp(-(K_value(i,3)*10)^2/((0.2^2)*2)); % compute the center of gravity if K_value(i,4)>0.5 Grave_Point_x=Grave_Point_x+1*(Points(1+(i-1)*3,1)... +Points(2+(i-1)*3,1)+Points(3+(i-1)*3,1)); Grave_Point_y=Grave_Point_y+1*(Points(1+(i-1)*3,2)... +Points(2+(i-1)*3,2)+Points(3+(i-1)*3,2)); Grave_K=Grave_K+1; end fake_saliency = Line2image(fake_saliency, K_value(i,4),... Points(((1+(i-1)*3):(3+(i-1)*3)),:));endI=rgb2gray(orgimage);BW= edge(I,'canny',0.1);subplot(132);imshow(BW); title('Forgery line detection');hold on;for i=1:line_number if K_value(i,4)>0.5 % line detection with S>0.5 plot(Points((1+(i-1)*3),1),Points((1+(i-1)*3),2),'Color', [1,0,0]); plot(Points((2+(i-1)*3),1),Points((2+(i-1)*3),2),'Color', [1,0,0]); plot(Points((3+(i-1)*3),1),Points((3+(i-1)*3),2),'Color', [1,0,0]); line([Points((1+(i-1)*3),1) Points((2+(i-1)*3),1)], [Points((1+(i-1)*3),2) Points((2+(i-1)*3),2)],... 'Color', [1,0,0], 'LineWidth', 3) line([Points((2+(i-1)*3),1) Points((3+(i-1)*3),1)], [Points((2+(i-1)*3),2) Points((3+(i-1)*3),2)],... 'Color', [1,0,0], 'LineWidth', 3) else plot(Points((1+(i-1)*3),1),Points((1+(i-1)*3),2),'Color', [0,1,0]); plot(Points((2+(i-1)*3),1),Points((2+(i-1)*3),2),'Color', [0,1,0]); plot(Points((3+(i-1)*3),1),Points((3+(i-1)*3),2),'Color', [0,1,0]); line([Points((1+(i-1)*3),1) Points((2+(i-1)*3),1)], [Points((1+(i-1)*3),2) Points((2+(i-1)*3),2)],... 'Color', [0,1,0], 'LineWidth', 3) line([Points((2+(i-1)*3),1) Points((3+(i-1)*3),1)], [Points((2+(i-1)*3),2) Points((3+(i-1)*3),2)],... 'Color', [0,1,0], 'LineWidth', 3) endend% Generate the fake saliency mapif Grave_K~=0 Grave_Point_x=round(Grave_Point_x/(Grave_K*3)); Grave_Point_y=round(Grave_Point_y/(Grave_K*3)); fake_saliency(Grave_Point_y-10:Grave_Point_y+10,... Grave_Point_x-10:Grave_Point_x+10)=255;endthick=max(size(fake_saliency,1),size(fake_saliency,2));fake_saliency = imdilate(fake_saliency,strel('ball',round(thick/30),round(thick/30)));fake_saliency = imfilter(fake_saliency,fspecial('gaussian', [round(thick/10) round(thick/10)], round(thick/10)));fake_saliency=im2double(fake_saliency);if Grave_K~=0 fake_saliency=fake_saliency.*(0.9/max(max(fake_saliency)));endsubplot(133);imshow(fake_saliency), colormap(hot); title('Fake saliency map');3 仿真结果4 参考文献[1] Fu, H. , and  X. Cao . "Forgery Authentication in Extreme Wide-Angle Lens Using Distortion Cue and Fake Saliency Map." IEEE Transactions on Information Forensics & Security 7.4(2012):1301-1314.博主简介：擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真，相关matlab代码问题可私信交流。部分理论引用网络文献，若有侵权联系博主删除。

七、图的算子1、属性算子类似于RDD的 map 操作scala> graph.mapEdges(e=>(e.srcId,e.dstId,e.attr+50)).edges.collect res16: Array[org.apache.spark.graphx.Edge[(org.apache.spark.graphx.VertexId, org.apache.spark.graphx.VertexId, Int)]] = Array(Edge(1,2,(1,2,550)), Edge(1,3,(1,3,650)), Edge(2,4,(2,4,650)), Edge(3,2,(3,2,150)), Edge(3,4,(3,4,1050)), Edge(3,5,(3,5,850))) // 解构语法 scala> graph.mapVertices{case (vid,(city,template))=>(vid,(city,template+3))}.vertices.collect res17: Array[(org.apache.spark.graphx.VertexId, (org.apache.spark.graphx.VertexId, (String, Int)))] = Array((4,(4,(上海,41))), (1,(1,(南京,43))), (3,(3,(北京,18))), (5,(5,(杭州,26))), (2,(2,(天津,15))))2、结构算子// subgraph 在大的图里截取小图 两个变量，存的都是函数 // vpred 高阶函数写法 scala> graph.subgraph(vpred=(id,attr)=>attr._2>35).vertices.collect res2: Array[(org.apache.spark.graphx.VertexId, (String, Int))] = Array((4,(上海,38)), (1,(南京,40))) // epred scala> graph.subgraph(epred=x=>x.attr<500).triplets.collect res15: Array[org.apache.spark.graphx.EdgeTriplet[(String, Int),Int]] = Array(((3,(北京,15)),(2,(天津,12)),100)) // 结合理解 scala> def xxx(a:Long,b:Tuple2[String,Integer]):Boolean={ | b._2<500 | } xxx: (a: Long, b: (String, Integer))Boolean scala> println(xxx(10L,("abc",300))) true // abc函数 当作变量传进 subgraph 函数 scala> def abc(id:VertexId,attr:Tuple2[String,Int]):Boolean={ | attr._2>35 | } scala> graph.subgraph(vpred=abc).vertices.collect res19: Array[(org.apache.spark.graphx.VertexId, (String, Int))] = Array((4,(上海,38)), (1,(南京,40)))3、Join 算子从外部的RDDs加载数据，修改顶点属性scala> graph.triplets.collect res20: Array[org.apache.spark.graphx.EdgeTriplet[(String, Int),Int]] = Array(((1,(南京,40)),(2,(天津,12)),500), ((1,(南京,40)),(3,(北京,15)),600), ((2,(天津,12)),(4,(上海,38)),600), ((3,(北京,15)),(2,(天津,12)),100), ((3,(北京,15)),(4,(上海,38)),1000), ((3,(北京,15)),(5,(杭州,23)),800)) scala> val ngp = sc.parallelize(Array((1L,30),(2L,60))) ngp: org.apache.spark.rdd.RDD[(Long, Int)] = ParallelCollectionRDD[52] at parallelize at <console>:27 scala> graph.joinVertices(ngp)((id,oldval,newval)=>(oldval._1,oldval._2+newval)) res22: org.apache.spark.graphx.Graph[(String, Int),Int] = org.apache.spark.graphx.impl.GraphImpl@4f134331 scala> graph.outerJoinVertices(ngp)((id,oldval,newval)=>(oldval._1,newval)).triplets.collect res24: Array[org.apache.spark.graphx.EdgeTriplet[(String, Option[Int]),Int]] = Array(((1,(南京,Some(30))),(2,(天津,Some(60))),500), ((1,(南京,Some(30))),(3,(北京,None)),600), ((2,(天津,Some(60))),(4,(上海,None)),600), ((3,(北京,None)),(2,(天津,Some(60))),100), ((3,(北京,None)),(4,(上海,None)),1000), ((3,(北京,None)),(5,(杭州,None)),800))八、GraphX API 的应用计算用户粉丝数量scala> graph.mapVertices{case (id,(city,tmp))=>City(city,tmp)}.triplets.collect res28: Array[org.apache.spark.graphx.EdgeTriplet[City,Int]] = Array(((1,City(南京,40)),(2,City(天津,12)),500), ((1,City(南京,40)),(3,City(北京,15)),600), ((2,City(天津,12)),(4,City(上海,38)),600), ((3,City(北京,15)),(2,City(天津,12)),100), ((3,City(北京,15)),(4,City(上海,38)),1000), ((3,City(北京,15)),(5,City(杭州,23)),800)) //outerJoinVertices()会join所有的点，没有匹配上的的返回None scala> val cc = sc.parallelize(Array((1L,20),(2L,30))) //getOrElse(0)匹配上的用，没有的返回None scala> graph.outerJoinVertices(cc)((id,oldv,newv)=>(oldv._1,newv.getOrElse(0))).triplets.collect res44: Array[org.apache.spark.graphx.EdgeTriplet[(String, Int),Int]] = Array(((1,(南京,20)),(2,(天津,30)),500), ((1,(南京,20)),(3,(北京,0)),600), ((2,(天津,30)),(4,(上海,0)),600), ((3,(北京,0)),(2,(天津,30)),100), ((3,(北京,0)),(4,(上海,0)),1000), ((3,(北京,0)),(5,(杭州,0)),800)) // join 只对相关联的代码进行操作 scala> graph.joinVertices(cc)((id,oldv,newv)=>(oldv._1,newv)).triplets.collect res35: Array[org.apache.spark.graphx.EdgeTriplet[(String, Int),Int]] = Array(((1,(南京,20)),(2,(天津,30)),500), ((1,(南京,20)),(3,(北京,15)),600), ((2,(天津,30)),(4,(上海,38)),600), ((3,(北京,15)),(2,(天津,30)),100), ((3,(北京,15)),(4,(上海,38)),1000), ((3,(北京,15)),(5,(杭州,23)),800)) // 出入度统计 // 样例类 case class City(name:String,tmp:Int,inNum:Int,outNum:Int) val find = graph.mapVertices{case (id,(city,tmp))=>City(city,tmp,0,0)} find.joinVertices(find.inDegrees)((id,oldval,newval)=>City(oldval.name,oldval.tmp,newval,oldval.outNum)).joinVertices(find.outDegrees)((id,oldval,newval)=>City(oldval.name,oldval.tmp,oldval.inNum,newval)).vertices.collect res43: Array[(org.apache.spark.graphx.VertexId, City)] = Array((4,City(上海,38,2,0)), (1,City(南京,40,0,2)), (3,City(北

文章目录一、概述1.1 Kafka Streams1.2 Kafka Streams 特点1.3 为什么要有 Kafka Streams二、Kafka Streams 数据清洗案例0）需求1）需求分析2）案例实操三、总结一、概述1.1 Kafka StreamsKafka Streams。Apache Kafka 开源项目的一个组成部分。是一个功能强大，易于使用的 库。用于在 Kafka 上构建高可分布式、拓展性，容错的应用程序。1.2 Kafka Streams 特点1. 功能强大高扩展性，弹性，容错2. 轻量级无需专门的集群一个库，而不是框架3. 完全集成100%的 Kafka 0.10.0 版本兼容易于集成到现有的应用程序4. 实时性毫秒级延迟并非微批处理窗口允许乱序数据允许迟到数据1.3 为什么要有 Kafka Streams当前已经有非常多的流式处理系统，最知名且应用最多的开源流式处理系统有 Spark Streaming 和 Apache Storm。Apache Storm 发展多年，应用广泛，提供记录级别的处理能力， 当前也支持 SQL on Stream。而 Spark Streaming 基于 Apache Spark，可以非常方便与图计算， SQL 处理等集成，功能强大，对于熟悉其它 Spark 应用开发的用户而言使用门槛低。另外， 目前主流的 Hadoop 发行版，如 Cloudera 和 Hortonworks，都集成了 Apache Storm 和 Apache Spark，使得部署更容易。既然 Apache Spark 与 Apache Storm 拥用如此多的优势，那为何还需要 Kafka Stream 呢？主要有如下原因。第一，Spark 和 Storm 都是流式处理框架，而 Kafka Streams 提供的是一个基于 Kafka 的 流式处理类库。框架要求开发者按照特定的方式去开发逻辑部分，供框架调用。开发者很难 了解框架的具体运行方式，从而使得调试成本高，并且使用受限。而 Kafka Streams 作为流式处理类库，直接提供具体的类给开发者调用，整个应用的运行方式主要由开发者控制，方便使用和调试。第二，虽然 Cloudera 与 Hortonworks 方便了 Storm 和 Spark 的部署，但是这些框架的部署仍然相对复杂。而 Kafka Streams 作为类库，可以非常方便的嵌入应用程序中，它对应用的打包和部署基本没有任何要求。第三，就流式处理系统而言，基本都支持 Kafka 作为数据源。例如 Storm 具有专门的 kafka-spout，而 Spark 也提供专门的 spark-streaming-kafka 模块。事实上，Kafka 基本上是主流的流式处理系统的标准数据源。换言之，大部分流式系统中都已部署了 Kafka，此时使用 Kafka Streams 的成本非常低。第四，使用 Storm 或 Spark Streaming 时，需要为框架本身的进程预留资源，如 Storm 的 supervisor 和 Spark on YARN 的 node manager。即使对于应用实例而言，框架本身也会占 用部分资源，如 Spark Streaming 需要为 shuffle 和 storage 预留内存。但是 Kafka 作为类库不 占用系统资源。第五，由于 Kafka 本身提供数据持久化，因此 Kafka Streams 提供滚动部署和滚动升级以 及重新计算的能力。第六，由于 Kafka Consumer Rebalance 机制，Kafka Stream 可以在线动态调整并行度。二、Kafka Streams 数据清洗案例0）需求实时处理单词带有”>>>”前缀的内容。例如输入”aaa>>>bbb”，最终处理成 “bbb”1）需求分析2）案例实操创建一个工程，并添加 jar 包创建主类package com.atguigu.kafka.stream; import java.util.Properties; import org.apache.kafka.streams.KafkaStreams; import org.apache.kafka.streams.StreamsConfig; import org.apache.kafka.streams.processor.Processor; import org.apache.kafka.streams.processor.ProcessorSupplier; import org.apache.kafka.streams.processor.TopologyBuilder; public class Application { public static void main(String[] args) { // 定义输入的 topic String from = "first"; // 定义输出的 topic String to = "second"; // 设置参数 Properties settings = new Properties(); settings.put(StreamsConfig.APPLICATION_ID_CONFIG, "logFilter"); settings.put(StreamsConfig.BOOTSTRAP_SERVERS_CONFIG, "hadoop102:9092"); StreamsConfig config = new StreamsConfig(settings); // 构建拓扑 TopologyBuilder builder = new TopologyBuilder(); builder.addSource("SOURCE", from) .addProcessor("PROCESS", new ProcessorSupplier<byte[], byte[]>() { @Override public Processor<byte[], byte[]> get() { // 具体分析处理 return new LogProcessor(); } }, "SOURCE") .addSink("SINK", to, "PROCESS"); // 创建 kafka streams KafkaStreams streams = new KafkaStreams(builder, config); streams.start(); } } 具体业务处理package com.atguigu.kafka.stream; import org.apache.kafka.streams.processor.Processor; import org.apache.kafka.streams.processor.ProcessorContext; public class LogProcessor implements Processor<byte[], byte[]> { private ProcessorContext context; @Override public void init(ProcessorContext context) { this.context = context; } @Override public void process(byte[] key, byte[] value) { String input = new String(value); // 如果包含“>>>”则只保留该标记后面的内容 if (input.contains(">>>")) { input = input.split(">>>")[1].trim(); // 输出到下一个topic context.forward("logProcessor".getBytes(), input.getBytes()); }else{ context.forward("logProcessor".getBytes(), input.getBytes()); } } @Override public void punctuate(long timestamp) { } @Override public void close() { } }（4）运行程序（5）在 hadoop104 上启动生产者[root@hadoop104 kafka]$ bin/kafka-console-producer.sh \ --broker-list hadoop102:9092 --topic first >hello>>>world >>aaa>>>bbb >>hahaha （6）在 hadoop103 上启动消费者[root@hadoop103 kafka]$ bin/kafka-console-consumer.sh \ --zookeeper hadoop102:2181 --from-beginning --topic second world bbb hahaha三、总结Kafka Streams的并行模型完全基于Kafka的分区机制和Rebalance机制，实现了在线动态调整并行度；同一Task包含了一个子Topology的所有Processor，使得所有处理逻辑都在同一线程内完成，避免了不必的网络通信开销，从而提高了效率;through方法提供了类似Spark的Shuffle机制，为使用不同分区策略的数据提供了Join的可能；log compact提高了基于Kafka的state store的加载效率；state store为状态计算提供了可能；基于offset的计算进度管理以及基于state store的中间状态管理为发生Consumer rebalance或Failover时从断点处继续处理提供了可能，并为系统容错性提供了保障；KTable的引入，使得聚合计算拥用了处理乱序问题的能力；

论文标题：Rumor Detection on Social Media with Bi-Directional Graph Convolutional Networks论文链接：https://arxiv.org/abs/2001.06362论文来源：AAAI 2020一、概述传统的谣言检测方法缺乏从谣言的传播（propagation）和扩散（propagation）结构中学习的高层表示。最近的研究已经开始从谣言的传播结构中学习高层表示，比如RvNN等方法。然而这些方法只关注谣言的传播却忽略了谣言扩散的影响。虽然一些方法已经开始尝试使用CNN来引入谣言扩散信息，但是基于CNN的方法只能捕获局部邻域的相关特征，却不能处理图或树结构中的全局结构关系，因此谣言扩散的全局结构特征在这些方法中被忽略了。事实上CNN也并非被设计用来从结构化的数据中学习高层特征，不过图卷积网络（Graph Convolutional Network,GCN）可以做到。GCN已经在很多领域取得了成功，不过我们不能简单地将GCN应用到谣言检测任务上。如下图(a)所示，GCN，或者称为无向GCN（UD-GCN）聚合信息只依赖相关帖子的关系却丢失了贴子之间的顺序关系： GCNUD-GCN虽然可以处理谣言扩散的全局结构特征，但是忽略了谣言传播的方向。沿着关系链的深度传播与社区群体内部的广度扩散是谣言的连个主要特点，因此需要一个方法来同时处理这两种传播方式。本文提出了Bi-GCN方法来同时处理谣言的传播与扩散。Bi-GCN同时在top-down和bottom-up的图结构上进行操作，具体的通过top-down GCN（TD-GCN）来处理谣言的传播，以及通过bottom-up GCN（BU-GCN）来处理谣言的扩散。如上图(b)(c)所示，TD-GCN从父亲节点到子节点前向传播信息来模拟谣言的传播，BU-GCN从节点的子节点聚合信息来表示谣言的扩散过程。二、方法问题陈述图卷积网络GCN的卷积操作被看做是一个消息传递（message-passing）的结构：Bi-GCN谣言检测模型Bi-GCN的核心思想是学习谣言传播和扩散的高层表示，在本文中采用的GCN都是用两层上述图卷积层。下图展示了模型的整个流程，主要分为4步： Bi-GCN构建传播和扩散图计算高层节点表示根节点特征增强谣言分类的传播和扩散表示谣言的传播和扩散表示通过聚合TD-GCN和BU-GCN的节点表示来获得，采用mean-pooling的方式：然后拼接这两个表示：三、实验数据集在Weibo,Twitter15,Twitter16三个数据集上进行实验，数据集统计如下： 数据集性能对比以下是在三个数据集上的结果： Weibo Twitter15和Twitter16消融实验对比不同架构和有无根节点特征增强对模型性能的影响： 消融实验谣言早期检测谣言传播的不同时期所达到的模型性能： 谣言早期检测

写在前面：我是「云祁」，一枚热爱技术、会写诗的大数据开发猿。昵称来源于王安石诗中一句 [ 云之祁祁，或雨于渊 ] ，甚是喜欢。​​写博客一方面是对自己学习的一点点总结及记录，另一方面则是希望能够帮助更多对大数据感兴趣的朋友。如果你也对 数据中台、数据建模、数据分析以及Flink/Spark/Hadoop/数仓开发 感兴趣，可以关注我的动态 https://blog.csdn.net/BeiisBei ，让我们一起挖掘大数据的价值~​​每天都要进步一点点，生命不是要超越别人，而是要超越自己！ (ง •_•)ง文章目录一、Flink 简介二、Flink 的重要特点2.1 事件驱动型(Event-driven)2.2 流与批的世界观2.3 分层api三、Flink 几大模块四、Flink vs Spark Streaming一、Flink 简介Flink 起源于 Stratosphere 项目，Stratosphere 是在 2010~2014 年由 3 所地处柏林的大学和欧洲的一些其他的大学共同进行的研究项目，2014 年 4 月 Stratosphere 的代码被复制并捐赠 给了 Apache 软件基 金会， 参加 这个 孵化项目的初始成员是Stratosphere 系统的核心开发人员，2014 年 12 月，Flink 一跃成为 Apache 软件基金会的顶级项目。在德语中，Flink 一词表示快速和灵巧，项目采用一只松鼠的彩色图案作为 logo，这不仅是因为松鼠具有快速和灵巧的特点，还因为柏林的松鼠有一种迷人的红棕色，而 Flink 的松鼠 logo 拥有可爱的尾巴，尾巴的颜色与 Apache 软件基金会的 logo 颜色相呼应，也就是说，这是一只 Apache 风格的松鼠。Flink 项目的理念是：“Apache Flink 是为分布式、高性能、随时可用以及准确的流处理应用程序打造的开源流处理框架”。Apache Flink 是一个框架和分布式处理引擎，用于对无界和有界数据流进行有状态计算。Flink 被设计在所有常见的集群环境中运行，以内存执行速度和任意规模来执行计算。二、Flink 的重要特点2.1 事件驱动型(Event-driven)事件驱动型应用是一类具有状态的应用，它从一个或多个事件流提取数据，并根据到来的事件触发计算、状态更新或其他外部动作。比较典型的就是以 kafka 为代表的消息队列几乎都是事件驱动型应用。与之不同的就是 SparkStreaming 微批次，如图：事件驱动型：2.2 流与批的世界观批处理的特点是有界、持久、大量，非常适合需要访问全套记录才能完成的计算工作，一般用于离线统计。流处理的特点是无界、实时, 无需针对整个数据集执行操作，而是对通过系统传输的每个数据项执行操作，一般用于实时统计。在 spark 的世界观中，一切都是由批次组成的，离线数据是一个大批次，而实时数据是由一个一个无限的小批次组成的。而在 flink 的世界观中，一切都是由流组成的，离线数据是有界限的流，实时数据是一个没有界限的流，这就是所谓的有界流和无界流。无界数据流：无界数据流有一个开始但是没有结束，它们不会在生成时终止并提供数据，必须连续处理无界流，也就是说必须在获取后立即处理 event。对于无界数据流我们无法等待所有数据都到达，因为输入是无界的，并且在任何时间点都不会完成。处理无界数据通常要求以特定顺序（例如事件发生的顺序）获取 event，以便能够推断结果完整性。有界数据流：有界数据流有明确定义的开始和结束，可以在执行任何计算之前通过获取所有数据来处理有界流，处理有界流不需要有序获取，因为可以始终对有界数据集进行排序，有界流的处理也称为批处理。这种以流为世界观的架构，获得的最大好处就是具有极低的延迟。2.3 分层api最底层级的抽象仅仅提供了有状态流，它将通过过程函数（Process Function）被嵌入到 DataStream API 中。底层过程函数（Process Function） 与 DataStream API 相集成，使其可以对某些特定的操作进行底层的抽象，它允许用户可以自由地处理来自一个或多个数据流的事件，并使用一致的容错的状态。除此之外，用户可以注册事件时间并处理时间回调，从而使程序可以处理复杂的计算。实际上，大多数应用并不需要上述的底层抽象，而是针对核心 API（Core APIs） 进行编程，比如 DataStream API（有界或无界流数据）以及 DataSet API（有界数据集）。这些 API 为数据处理提供了通用的构建模块，比如由用户定义的多种形式的转换（transformations），连接（joins），聚合（aggregations），窗口操作（windows）等等。DataSet API 为有界数据集提供了额外的支持，例如循环与迭代。这些 API处理的数据类型以类（classes）的形式由各自的编程语言所表示。Table API 是以表为中心的声明式编程，其中表可能会动态变化（在表达流数据时）。Table API 遵循（扩展的）关系模型：表有二维数据结构（schema）（类似于关系数据库中的表），同时 API 提供可比较的操作，例如 select、project、join、group-by、 aggregate 等。Table API 程序声明式地定义了什么逻辑操作应该执行，而不是准确地确定这些操作代码的看上去如何。尽管 Table API 可以通过多种类型的用户自定义函数（UDF）进行扩展，其仍不如核心 API 更具表达能力，但是使用起来却更加简洁（代码量更少）。除此之外， Table API 程序在执行之前会经过内置优化器进行优化。你可以在表与 DataStream/DataSet 之间无缝切换，以允许程序将 Table API 与 DataStream 以及 DataSet 混合使用。Flink 提供的最高层级的抽象是 SQL 。这一层抽象在语法与表达能力上与 Table API 类似，但是是以 SQL 查询表达式的形式表现程序。SQL 抽象与 Table API交互密切，同时 SQL 查询可以直接在 Table API 定义的表上执行。目前 Flink 作为批处理还不是主流，不如 Spark 成熟，所以 DataSet 使用的并不是很多。Flink Table API 和 Flink SQL 也并不完善，大多都由各大厂商自己定制。实际上 Flink 作为最接近 Google DataFlow模型的实现，是流批统一的观点，所以基本上使用 DataStream 就可以了。三、Flink 几大模块Flink Table & SQL(还没开发完)Flink Gelly(图计算)Flink CEP(复杂事件处理)四、Flink vs Spark Streaming