超级大米

题解

/ 注册

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

题解 | #正则表达式匹配#

动态规划，把pattern预处理一下，*字符和前面的字符分成一组，就可以开始了，dp[i][j],表示str的前i个字符和pat（处理后的数组）的前n组字符是否能匹配上 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

C++ 动态规划

2021-12-29

0 394

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

动态规划，二维数组 comp[i][j] 项表示当str1的前i个字符匹配str2的前j个字符需要做的变化量。然后分两种情况，str1[i],str2[j]相同和不同，代码里应该很清楚了 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改...

C++ 动态规划

2021-12-29

0 319

题解 | #最长上升子序列(二)#

也算是一种动态规划新建一个数组，单调递增，数组中的数字upVec[i]表示长度为n的最小子序列，数组的长度就是最终子序列的长度。新来一个元素，如果他大于数组中的所有数字，则插入到末尾，否则，把第一个大于他的数字变成他。假设upVec = [1,3,5]，如果来了7，则变成 [1,3,5,7...

C++ 动态规划二分查找

2021-12-14

3 435

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

用到了动态规划和字典查询，f(n)表示从从0到第n个字符有哪些解，则f(n) = (字母(0到n)如果在字典中，则并入f(0)的解) + (字母(1到n)如果在字典中，则并入f(1)的解).... (字母(n-1到n)如果在字典中，则并入f(n-1)的解),最终输出f(n) class Soluti...

C++ 动态规划哈希表

2021-12-07

0 457