题干解析 题设给予我们一个数组，要求我们进行判定所给数组能够拆分为两个总和一致的数组。 算法思路 首先大前提，我们必须知道这个数组所有值的总和，记作sum，当且仅当sum是个偶数时我们才可能将数组拆分为两个等和子集。 同时我们转化问题为，在数组中选择一定数量的元素，使这些元素的总和大小为。于是我们将问题转化为0/1背包问题。设定状态值为dp[i][j]表示使用前i个元素能否填满大小为j的背包。 于是我们有状态转移方程：  设定初始值dp[0][0] = true;开始DP计算即可。 同时由于DP过程状态转移方程只涉及i与i-1，因此可进行滚动优化内存。 实现代码 class Solution ...

题干解析 题设给予我们两个字符串，我们每次能够对第一个字符串进行任意次以下操作之一：  删除一个字符 插入一个字符 更改一个字符 求将第一个字符串更改为第二个字符串的最少操作次数。  算法思路 设第一个字符串为s1，第二个为s2 我们定义二维状态数组dp[i][j]表示将s1的前i个字符字串更改为s2的前j个字符字串的最少操作次数。 不难得出如果针对s1[i]==s2[j]时，dp[i][j]=dp[i-1][j-1]，也就是说无需再进行操作，直接继承。 反之如果不成立，需要在原基础上进行一次操作：  删除一个字符操作：dp[i][j] = dp[i-1][j] + 1 插入一个字符操作：dp...

题干解析 题设给予我们6种砝码，分别个，要求我们返回这些砝码能够组成的总重种数。 算法思路 本题可以进行一些转化，我们设定我们有一个承重为i的背包，设定状态值dp[i]表示装满这个背包的方案数。由此我们能够将整个问题转化为求dp数组，最后统计dp数组种的非零值的个数然后输出即为答案。 通过以上转化，我们将问题转化为一个背包DP问题。理论上本题数据量不大，能够直接转化为0/1背包进行求解，以下内容为对其进行二进制优化后的解法，通过将总数进行二进制拆分，优化时间复杂度。 实现代码 #include <bits/stdc++.h> using namespace std; int mai...

题干解析 题设给予宝石总数(n)，背包空间大小（C）与每种宝石的价值(w)，每个宝石所占空间大小(c)与数量(m)，要求我们选择一种存储方式，使在不超过背包空间的前提下获得最大价值。 算法思路 多重背包问题。首先我们我们可以延续0/1背包的思路，将所有单个宝石看作一种宝石转化为0/1背包，这样做只需在原有的两层循环嵌入一层k从的循环即可。 但注意以上方案时间复杂度预计为最坏情况下n=100, 所有，总计进行数量级以上的计算，会超时，需要优化 一种简单的优化方向是进行二进制拆分后再转化为0/1背包。 假设某个宝石，我们不妨将25拆成集合，自行尝试一下，这五个数的任意组合的和能够覆盖0~25所有的...

题干解析 题设给予课程数N与学习天数M，且每门科目学习对应1-M天均有一定的收益，问如何分配学习时间使得最后的总收益最高，返回最高值。 算法思路 典型的分组背包DP问题。 我们定义状态值表示将前i类物品（这里是课程）放进容量为j的背包（这里是学习天数）可获得的最大价值。由此状态转移方程如下：  其中表示不装入第i类物品，表示依次装入第i类物品 对比普通0/1背包，只要内层循环增添关于k的一层即可。 实现代码 #include <iostream> #include <vector> #include <algorithm> using namespace s...

题干分析 题设给予我们一个人通过老式九键输入的按钮顺序字符串，已知老式九键输入模式为按对应的数字按键k次定位到该数字按键表示的三个或四个字母中的第k个进行输入（注意不会循环）。要求我们通过所给的按键顺序字串推测可能的输入内容总数（结果对取余） 算法思路 拆分问题： 首先考虑全部按键顺序字串只有一种按键的情况：  如果没有按任何按键，输入内容视作空，仍然看作一种情况 如果只按一次某按键，输入内容唯一，即所按按键对应的第一个字母 如果按两次，要么对应两次第一字母，要么对应一次第二字母，共2种情况 如果按三次，对应三个第一字母，对应一个第二一个第一，先后关系导致计数+2，以及一次第三字母，共计4种情...

题干分析 题设给予我们四个正整数（以下取首字母z,o,l,h），从一个空字符串我们可以进行若干次以下操作：  在字符串末尾接上z个字符'0' 在字符串末尾接上o个字符'1' 要求最后得到的字符串长度在区间内，求符合要求的字串数（模）  算法思路 拆分问题： 我们得到的最终字符串只可能从两种情况下得来：  通过一个字符串末尾添加z个字符'0' 通过一个字符串末尾添加o个字符'1'  设数组值dp[i]表示依据题设构造一个长为i的字符串的方法数，不难得到DP状态转移方程如下：  同时我们设定DP初始条件为 计算完成后将i从l循环递增到h求dp[i]的值之和输出即可。 注意全程在计算时需要追加模计算...

题干分析 题设给予我们一个可使用的正整数数组（数组内元素不重复）要求我们任意使用数组中的数组进排列，使得排列后所得的总和为给出的目标整数。求符合条件的排列总数。 算法思路 本题本质上是一个比较灵活的爬楼梯问题，我们可以将目标整数视作我们需要爬的楼梯总数，所给的正整数数组即为我们一步能够跨过的台阶数，计算排列的总数就理所应当的变为求爬上目标台阶数的方法数。 因此有DP状态转移方程：  以及初始条件：  实现代码 class Solution { public: int combinationSum4(vector<int>& nums, int target) { vecto...

题干分析 题设给予我们一个有限大小的背包，大小为V。同时给予我们n个骨头及其对应的价值与所占空间。求骨头收藏家使用该背包能够获得的最大骨头总价值。 算法思路 拆分问题： 我们首先考虑只装第一块骨头的情况：  背包大小从0~V递增的过程中不难证明当背包大小超过第一块骨头大小时将其塞入为最优策略。  接着我们尝试考虑放前两个骨头：我们只考虑第二块骨头  背包大小V不足以放下第二块骨头时直接继承只放第一块骨头的最优情况 背包大小V足以放下第二块，我们此时有两个选择：放下第二块与不放，不放的情况与只放一块骨头情况一致，放下第二块骨头则背包大小缩小为V-v[2]，此时子问题为在大小为V-v[2]大小的背...

题干分析 题设给定一个花费数组，已知我们可以上1/2/3级台阶，每次上到台阶i要花费costs[i]，同时根据上的台阶级数，追加花费1/4/9的花费。求从台阶0开始上到台阶n的最小花费为多少。 算法思路 拆分问题： 到达台阶n我们只能从台阶n-1/n-2/n-3开始分别花费对于的启动花费并追加移动花费到达台阶n。由此，我们设计dp[i]记录到达第i节台阶的最小花费，不难得到状态转移方程：  同时有初始条件：  同时我们注意到整个DP过程只涉及连续的四个状态值，因此可以进一步优化为常数额外空间消耗的迭代形式。 实现代码  递归与未进行内存优化的写法已注释  class Solution { /*...

题干分析 题设给定一个爬楼花费数组，记录每到一个台阶需要再向上爬所需的花费。要求我们求解从下标0或者1开始爬楼到达楼顶所需最小花费。 算法思路 基本的线性DP问题。根据题设我们可以假设初始我们从下标-1处出发，到下标0或者下标1，此次出发无花费。因此设数组表示到达下标为i的台阶所需花费，初始条件为：  我们的目标是到达楼顶，即求。 我们将总目标进行拆分：由于到达下下标为n的台阶只可能是从下标n-1的台阶上花费cost[n-1]上来，或者从下标n-2上花费cost[n-2]上来，我们取其中的最小值，由此DP状态转移方程为：  同时我们不难观测到整个DP状态转移过程只涉及相邻的三个DP状态，完全可...

题干分析 题设要求我们动态维护一个有序数据结构，并进行若干次6种操作。 算法思路 本题有两种解决思路，一种是放弃使用树状结构，直接使用STL库提供的二分查找算法与vector容器实现。 另一种思路是维护树状的二叉查找树进行实现，同时为了提高查找效率，我们得防止我们构建的树过于不平衡，也就是说我们需要动态维护一个平衡二叉搜索树。这里个人做法是实现一颗替罪羊树，设定一个不平衡率，只要子树达到该不平衡率我们就直接重建一颗相对平衡的子树。同时针对删除，我们采取懒删除方式标记删除节点，当树发生重建时再真正删除。 实现代码  使用STL库+vector容器实现：  #include <bits/st...

题干分析 题设给定我们一个二叉树，要求我们寻找其中的二叉搜索子树，并返回其中所有节点的节点总和的最大值。 算法思路 我们判断一颗树是否为二叉搜索树定义上是左子树节点严格小于根节点值，右子树节点严格大于根节点。 其实如果一颗二叉搜索树所有节点同时也满足左子树最大节点值小于根节点，右子树最小节点值大于根节点（前提是有左右子树）也可以判断其为二叉搜索树。依据此，我们后序遍历题设给予我们的树，找到左右子树的最小，最大与节点值总和。然后进行判断。 同时我们注意到，我们要求所有节点均需要满足条件才能成为二叉搜索树，因此只要出现不符合条件的子树，我们需要让这颗子树的返回值永远导致其父节点所属子树不为二叉搜索...

题干分析 利用二叉搜索树的定义转化一下即：题设给定一颗二叉搜索树，和一个查询值，要求我们找到最接近这个值的两个节点值，如果相等则返回两次节点值，如果为边界节点，另一节点值用-1代替。 算法思路 利用二叉搜索树的中序遍历结果为其所有节点值组成的升序数组的性质，将在二叉搜索树上的查找转化为数组中的二分查找第一个不小于给定值的元素。 注意，二叉搜索树可能退化为一条链，利用二叉搜索树的定义进行查找会超时。 实现代码 class Solution { void dfs(TreeNode *node, vector<int> &order) { if (node) { dfs(node...