CroMarmot

题解

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

/ 注册

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

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

编辑距离(二)（动态规划）题意给定两个字符串,把字符串str1编辑为str2的最小代价,其中插入(ic),删除(dc)和替换(rc)代价分别为给定常数思路分析顺序性无关证明设对str1有一系列操作, 对于一个被增加的字符,一定不会被删除和被修改对于一个被删除的字符,一定不会被增加和被修改...

C++ 动态规划

2022-02-02

0 521

题解 | #最长公共子串#

最长公共子子串（动态规划）题意给定两个字符串,求它们的最长公共子串思路分析公共子串要找s1和s2的公共子串,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的后缀公共子串加上相等的字符,就能得到一个更长的公共子串, 所以有, 令s[i][j]表示分...

C++ 动态规划

2022-02-02

1 290

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

最长公共子序列(二)（动态规划）题意给定两个字符串,求它们的最长公共序列思路分析公共序列要找s1和s2的公共序列,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的公共序列加上相等的字符,就能得到一个更长的公共序列, 所以有, 令s[i][j]表示...

C++ 动态规划

2022-02-02

13 579

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

最长上升子序列(三)（动态规划）题意给定一个正整数数组，求它的最长上升子序列，如果有多个，求数值字典序最小的思路分析上升子序列先不考虑最长，先考虑如何找到一个上升子序列每次对于一个值，去找它前面比它小的值就能构成最后把链输出就能得到上升子序列 for(int i = 0;i<ar...

C++ 动态规划

2022-01-31

1 440

题解 | #兑换零钱(一)#

兑换零钱（一）（动态规划）题意给定一个正整数数组，和一个目标值，问最少选取多少个数组中的值能使得其和等于目标值。其中每个值可以被选任意次思路分析最优关系的数学推导假设对于值aim有一个最优方案，这个最优方案中有选一次x,那么上述最优方案中去掉x的剩余的数，是aim-x的一个最优方案。 ...

C++ 动态规划

2022-01-30

0 387

题解 | #通配符匹配#

通配符匹配（动态规划）题意给一个字符串，和一个通配符表达式，问该字符串是否满足通配符表达式。其中，通配符表达式除了字符外，只支持两种通配符 ?匹配一个任意字符 *匹配任意个任意字符思路分析字符串相等比较如果直接比较两个字符串相等，是按位比较 for(int i = 0;i < le...

C++ 动态规划字符串

2022-01-28

0 513

题解 | #求路径#

求路径（动态规划）题意一个m⋅nm\cdot nm⋅n的地图,从左上角，只能向右或向下，走到右下角，有多少种方案。思路分析什么叫不同的方案呢? 如果把走动的方向，变成序列，两个序列不同，则是不同的方案。如图中红色的走动变成序列是(向右,向右,向右,向右,向下,向下,向下) 蓝色的走动序...

C++ 动态规划数学组合数

2022-01-28

0 335

题解 | #分割等和子集#

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

C++ 数组动态规划

2022-01-04

0 588

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

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

C++ 数组动态规划

2022-01-03

1 851

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

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

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

2022-01-03

0 815