华科不平凡

题解

/ 注册

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

最长的括号子串长度来自专栏

维护一个栈，保存左括号的下标，如果遇到右括号，则弹出一个左括号，并且更新长度。注意到一个特殊情况如(())()，我们需要保存栈空时的起始节点： // // Created by jt on 2020/8/31. // #include <stack> #include <iostr...

栈

2020-08-31

4 1176

通配符匹配来自专栏

为了描述方便，我们将s称为主串，p称为模式串三种思路：贪心（超时）回溯动态规划贪心（超时） // // Created by jt on 2020/8/31. // #include <cstring> #include <iostream> using na...

递归贪心动态规划

2020-08-31

6 1332

有障碍的矩阵最短路径数来自专栏

设dp[i][j]表示前i行和前j列最短路径数，状态方程如下：当i >= 2 && j >= 2时，如果obstacle[i-2][j-1] != 1, dp[i][j] += dp[i-1][j] 如果obstacle[i-1][j-2] != 1, dp[i][...

动态规划

2020-08-30

2 1144

矩阵路径数来自专栏

dp[i][j]表示前i行、j列的路径数，状态公式如下：如果i >= 2 && j >= 2，那么dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[1][k] = 1 dp[k][1] = 1 解释如下：当列数和行数大于2的时候，当前节...

动态规划

2020-08-30

7 1039

带权值的最小路径和来自专栏

设dp[i][j]表示行数为i，列数为j的矩阵中，从左上角到右下角的最小路径和。状态公式：当i>=2 && j>=2时，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1] 基准1: dp[1][k] = dp...

动态规划

2020-08-30

1 1032

爬楼梯来自专栏

两种方法：斐波那契数列（找规律——爬1层1种，2层2种，3层3种，4层5种...）动态规划有必要总结一下找规律的解法：这种解法需要细心和耐心，我们一般取出前3种情况看一下规律，如果规律不明显，可以增加情况，直到过于复杂才放弃此解法。PS：前几种情况同样可以用来检验算法的正确性动态规划...

斐波那契数列动态规划

2020-08-30

0 882

最小编辑距离来自专栏

dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。状态公式：如果word1[i-1] = word2[j-1]，dp[i][j] = dp[i-1][j-1] 如果word1[i-1] != word2[j-1], dp[i][j] = min(dp[i-1...

动态规划

2020-08-30

0 1028

判断乱序字符串来自专栏

牛客的标签里面有“动态规划”，搞得我一脸懵逼😳 本题应该用递归/贪心实现，条件如下：基准1: 如果两个字符串长度不相等，返回false 基准2: 如果两个字符串相等，返回false 基准3: 如果两个字符串中对应字符的个数不相等，返回false 递归判断子字符串是否是乱序字符串代码如下： ...

递归贪心

2020-08-30

0 883

购物单（背包问题）来自专栏

出题者觉得0/1背包太套路了，因此给我们使了点小绊子，但是问题不大。设主件个数为n，奖金数量为M，每个主件对应的价格为v，每个主件对应的重要程度为w。d[i][j]表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有0～2个附件，最多...

背包问题动态规划

2020-08-27

324 15888

最少邮票个数来自专栏

首先，这是一个背包问题。描述转化为“背包”，有N个物品，每个物品的质量为Vi，背包重量为M，求最少取多少个物品才能刚好装满背包，如果无法满足条件，返回0。我们用INT32_MAX表示无法凑齐，设dp[i][j]为邮票为前i张时，刚好凑成j所需要的最小邮票张数，有以下状态公式：当j-v[i-1]...

背包问题动态规划

2020-08-27

1 760