CroMarmot

分类

未归档(12) 题解(138) 题解总结(4)

/ 注册

全部文章（共34篇）

题解 | #分割等和子集#

题意给一个非负数组，问能否把数组分成两部分，让两部分的和相等限制：数组长度不大于200 数组的每个值不大于100 方法递推要让分割的两部分和相等，也就是其中一部分的和等于整个数组的和的一半。那么可以考虑去求一部分数组能达成哪些和考虑用aval[i][j]=true/false表示，前i...

C++ 数组动态规划

2022-01-04

0 576

题解 | #编辑距离(一)#

题意字符串A最少需要多少次, 插入/删除/修改能变成字符串B 限制,两个字符串长度均不超过500500500 方法递推+状态设计状态 dp[i][j] 表示,地一个字符串的前i个最少操作dp[i][j]次能变成第二个字符串前j 那么有状态转移 A[i]=B[j]时,对应位置字符相等,直接匹配...

C++ 数组动态规划

2022-01-03

1 831

题解 | #压缩字符串(二)#

题意给定字符串,和最多可以先删除的字符数量,再对它进行连续字符的压缩,求压缩后字符串的最短长度限制: 原字符串长度不大于100 方法 dfs(TLE) 题目拆解为两部分字符串删除压缩字符串对于字符串删除字符的部分,采用深度搜索的方式, 每层记录,当前遍历的字符串位置,还可以删除的字符串...

C++ 字符串动态规划数组

2022-01-03

0 784

题解 | #单词拆分(一)#

题意给定字符串能否由给定字典中的单词拼接而成. 限制: 字符串长度不大于500 字典单词数不大于1000,每个单词长度不大于20 方法 dfs 通过递归,每次匹配字典里所有单词,一旦匹配成功, 从匹配成功的下标递归搜索下一个位置,如果完全匹配了则返回匹配成功. 代码 class Solution ...

C++ 字符串数组动态规划

2022-01-03

0 443

题解 | #数组分组#

题意一个数组分成两组 5的倍数在一组是3的倍数且不是5的倍数在另一组剩余数字自由分组是否能让分成的两组数字的和相等限制：数组长度不大于50，数值绝对值不大于500 方法动态规划先不考虑限制，分成两组和相等，也就是两组数字和的差为0,即是第一组的和 - 第二组的和 = 0 再看...

C++ 动态规划数组

2021-12-08

0 424

题解 | #计算字符串的距离#

题意给两个字符串，求最小编辑次数让两个字符串相等。其中编辑允许的操作增加一个字符修改一个字符删除一个字符限制：每个字符串长度小于500 方法动态规划考虑设计状态 dp[i][j] 表示，第一个字符串s匹配了i个字符，第二个字符串t匹配了j个字符的最小编辑代价那么有转移方程 dp...

C++ 动态规划

2021-11-02

0 393

题解 | #合唱队#

题意给定一个数列,问最少删除多少个数,使得数列为先严格单调递增后严格单调递减的数列. 限制:有多组数据,每组数列个数不大于3000 方法双重循环要删除的人最少,就是要留下的人最多,所以我们以要留下的人最多的来思考一个严格单调递增,再严格单调递减的序列,不妨把它拆分成两部分处理. 如果我们能计...

C++ 动态规划数组二分查找

2021-10-24

1 551

题解 | #牛妹的招聘#

题意给两个等长的数组。选择一系列坐标，使得两个数组对应位置分别的和非负，且对应位置的值总和最大。求这个最大值。范围：数组长度最大100，数值绝对值<1000 < 1000<1000 样例有误应该是11 方法 dfs(TLE) 我们通过深搜，遍历每一个人选择或者不选择。遍历到...

C++ 动态规划

2021-10-05

0 453

题解 | #取球放球#

题意给一个有初始值的数组，并且其中每个位置单独限定最大值。每次操作可以给任意一个位置在[0~最大值]的范围内加一减一问在不超过k次操作后，相邻项的差的平方的最大值，最小为多少算法动态规划（TLE）首先，虽然题目求的是相邻项差的平方的最大值的最小值。实际上绝对值越大平方越大，所以我们可以改...

C++ 动态规划前缀和

2021-10-04

0 390

题解 | #牛妹的面试#

题意给定数组。找一个子序列，满足先严格递增后严格递减，求最大的子序列长度数组长度 ≤1000\leq 1000≤1000 方法 dfs(TLE) 我们枚举每一个位置，假设这个位置是顶点，从这个顶点向两侧深度搜索。搜索的设计为，遍历点。如果一个点可选，则考虑选择改点并继续深搜，深搜返回后遍历...

C++ Python3 动态规划

2021-10-04

0 423