赫he

分类

题解(3)

/ 注册

全部文章（共55篇）

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

假设两个字符串分别是a和b。dp[i][j]表示所有将a[1~i]变成 b[1~j]的操作方式的最少次数。对于状态dp[i][j]可以怎么划分呢？从三个操作的角度考虑：1）删除操作：a的[1~i-1]==b的[1~j]，删除a中第i个字符，a[1~i]和b[1~j]就变成一样了==》f[i][j...

2023-06-19

0 235

题解 | #最长公共子序列(一)#

设dp[i][j]表示 1~i的s1子串和1~j的s2子串的最长公共子序列的最大长度思想：从哪里来如果s1[i]==s2[j]了，那这个f[i][j] = max(f[i][j], f[i-1][j-1]+1)如果s1[i]!=s2[j]f[i][j] <-- max( f[i-1][j], ...

2023-06-19

0 281

题解 | #信封嵌套#

按照长度从小到大排序，当长度相同时，按照宽度从大到小排序。在宽度的维度上，动态规划求最长上升子序列的长度为什么能这么做呢？首先，宽度的维度上，动态规划求最长上升子序列在长度方向上肯定也是从小到大的。这里面不存在相等的长度，因为本身上升子序列是一种递增的顺序，而如果长度相同了，它的对应的宽度是第减...

2023-06-15

0 254

题解 | #合唱队形#

关键找第i个，1~i 是一种递增的顺序， i~k是递减的顺序最少几位出列：找一个i 使得递增序列的长度和递减序列的长度和最大那就枚举每个i 作为那个队形中最高值的情况。这样i之前就是求以h[i]为结尾的最长递增子序列的长度，就是求一遍数组的最长子序列，对应的f[i]自然就表示了“h[i...

2023-06-12

0 303

题解 | #拦截导弹#

等价于求两个问题：问题1：求最长不增（小于等于）子序列的长度方面就是线性dp问题2：求最少可以划分出不增（小于等于）子序列的个数 #include <iostream> #include <set> using namespace std; const int N =...

2023-06-09

0 306

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

#include <iostream> #include <cstring> using namespace std; int dp[1010]; int main() { int n; cin >> n; int arr[n]; ...

2023-06-08

0 237

题解 | #矩阵的最小路径和#

#include <iostream> #include <cstring> using namespace std; const int N = 501; int map[N][N]; int dp[N][N]; //其中 dp[i][j]表示到位置(i,j)时的最小路...

2023-06-06

0 274

题解 | #最大子矩阵# 枚举

#include <climits> #include <cstdio> #include <iostream> #include <string.h> using namespace std; const int N = 105; int map[N...

2023-06-05

0 255

题解 | #连续子数组最大和#

#include <iostream> using namespace std; const int N = 200010; int dp[N]; //dp[i] 表示数组 1~i满足的最大值 int a[N]; int main() { int n; sc...

2023-06-01

0 271

题解 | #跳台阶扩展问题#

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> using namespace std; int main() { int n;...

2023-05-31

0 253