CroMarmot

题解

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

/ 注册

全部文章 / 题解（共31篇）

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

题意给定字符串能否由给定字典中的单词拼接而成. 限制: 字符串长度不大于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 444

题解 | #取球放球#

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

C++ 动态规划前缀和

2021-10-04

0 391

题解 | #牛妹的面试#

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

C++ Python3 动态规划

2021-10-04

0 423

题解 | #牛妹的礼物#

题意给一个n⋅mn\cdot mn⋅m的二维数组，从左上向右下走，只能i+=1i+=1i+=1或j+=1j+=1j+=1或同时i+=1,j+=1i+=1,j+=1i+=1,j+=1 求经过的块的值的和的最小值。其中 nnn和mmm 最大取到300300300 每个块是非负值，最大取到100100...

C++ Python3 动态规划

2021-10-03

0 372

题解 | #牛能和牛可乐的礼物#

题意给定数组presentVecpresentVecpresentVec，把数组拆分成两个子数组，使得两个子数组分别的和的差最小。范围，数组长度n≤100n \leq 100n≤100, 所有值111到100100100之间方法深搜(TLE) 代码我们可以枚举所有的选择方案，选或者不选。 ...

C++ Python3 动态规划

2021-10-03

0 397

题解 | #单帧操作#

题意长度为nnn的数组, 每次把相邻的三个数，都变为它们中的最大值，操作的下标从左向右问，操作iii次后的数组的最大和, 其中iii从111取到nnn,给出不同iii对应的最大值。 n≤200n\leq 200n≤200 数组中每个数值111到200200200之间的整数算法深搜(TLE) ...

C++ Python3 动态规划递推

2021-10-02

0 390