daydayup牛

题解

/ 注册

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

题解 | #字符串通配符#

37行完美解决，力扣44动态规划，只是这道题多了其他符号，那么其它符号就应该单独考虑动态规划代码比较难以理解，下面详细解释。 #include <algorithm> #include <vector> using namespace std; int main() {...

C++ 动态规划

2022-03-30

18 540

题解 | #查找两个字符串a,b中的最长公共子串#

压缩一下，空间复杂度一下就降下来了，不停的更新每一行就行了，把短的字符串弄到第一行。其实可以看出有公共子串其实就是矩阵里不为0的位置连在一起。 ```#include <iostream> #include <algorithm> #include <vector&...

C++ 动态规划字符串

2022-03-25

0 364

题解 | #查找两个字符串a,b中的最长公共子串#

动态规划，以第i和j个字符结尾的公共子串若存在则长度为dp[i][j]，若str1[i]==str2[j]则dp[i][j]=dp[i-1][j-1]+1。求出最长并输出就行了，这个动态规划还可以压缩 #include <algorithm> #include <vector>...

C++ 动态规划

2022-03-25

0 308

题解 | #数组分组#

动态规划，想办法转化力扣的416题，分割相等其实就是找一个集合使它们中有数的组合可以加起来等于某个数，而这个数在416题是和的一半，我这里就是x/2 #include <algorithm> #include <vector> using namespace std; b...

C++ 动态规划

2022-03-25

0 353

题解 | #公共子串计算#

用压缩数组节省空间，只保留一行，利用动态规划的无后效性。空间复杂度O(N) #include <algorithm> #include <vector> using namespace std; int main() { string str1,str2; ...

C++ 动态规划

2022-03-22

2 459

题解 | #放苹果#

####这道题要注意边界条件，苹果和盘子那里的转移方程不太好理解，我尝试着解释一下，详情看代码 #include <algorithm> #include <vector> using namespace std; int main() { int m,n; ...

C++ 动态规划

2022-03-22

7 401

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

这是一维的压缩情况，该篇仅在你搞懂二维的动态规划方可解锁，详见注释 #include <algorithm> #include <vector> using namespace std; int main() { string str1,str2; whi...

C++ 动态规划

2022-03-21

0 295