相关知识点

C++算法与数据结构

打开打包代码的方法兼述单元测试

这个算法很容易想到，学习了本文后，可以更快得想到。

前后缀分解

分治法的一种，将数组和字符串，拆分成前缀和后缀。字符串(数组）的前缀是字符串的前i个元素：s.substr(0,i-1)，即s[0]

…

\dots

… s[i-1]。同理后缀就是字符串s的后几个元素（字符）。

不失一般型，我们以字符串s=“abcde"为例，s有5种拆分方法：

如果字符串的长度为n，则共有n+1中划分法，前缀长度分别为：i

∈

\in

∈[0,n]，后缀长度分别为n-i。

一般分三步：

一，预处理前缀。

二，预处理后缀。

三，枚举前后缀的拆分方法。

取走水果

条桌上有若干梨和苹果，求最少取走多少水果，才能没有苹果在梨左边。我们将水果分成左（前缀)、右(后缀)两部分，前缀只有梨，取走所有苹果；后缀只有苹果，取走所有梨。分别枚举前缀的长度。如下图，初始梨苹果梨苹果梨，各划分方案：红色竖线之前是梨，红色竖线之后是苹果：

转置字符串（数组)

将字符串s前后颠倒就是转置字符串revs，两者长度相等：

revs[i] = s [n-1-i]

字符串的前缀（后缀）就是转置字符串的后缀（前缀)，顺序相反。如："abcde"长度为3的前缀是：abcde，转置字符串长度为3的后缀是：edcba。许多时候和顺序无关，可以直接使用，如：子数组最大和、是否存在指定和的子数组、指定元素的数量。如果和顺序有关，则需要转换，比如：升序变成降序，起点变成终点。

二维数组处理起来麻烦，可以降维为一维数组后再处理。

相关题解

部分题解已经完成，逐步发布中。

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。