摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10952人学习

全部文章（共87篇）

题解 | #红和蓝# 来自专栏

题目的主要信息：一棵无向树，给每个顶点染成红色或蓝色每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点无法完成染色输出-1，完成染色输出每个结点的颜色具体做法：首先叶子结点因为只与父亲结点相连，所以叶子结点与父亲结点同色，因此我们可以利用dfs从根节点开始递归遍历树，从叶子结点...

C++ 动态规划 dfs

2021-11-01

1 833

题解 | #旅游# 来自专栏

题目的主要信息：地图上有 n 个城市，它们之间通过 n-1 条道路联通，即一棵无向树第一天会在 s 市住宿，并游览与它距离不超过 1 的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过 1 的所有城市不能住在一个已经浏览过的城市，最多要游览多少天因为每个会去到与这个城市相连...

C++ 动态规划 dfs

2021-11-01

9 594

题解 | #走方格的方案数# 来自专栏

题目的主要信息：一个n∗mn*mn∗m的表格，从左上角走到右下角的方法种数每次只能走下或者右不能回头方法一：递归具体做法：容易想到的是，在第一步时可以选择向右或者向下，只需要当前的路径选择上加上(n,m−1)(n,m-1)(n,m−1)和(n−1,m)(n-1,m)(n−1,m)的矩...

C++ 递归动态规划数学

2021-11-01

87 2477

题解 | #公共子串计算# 来自专栏

题目的主要信息：查找两个字符串a,b中的最长公共子串的长度字符串只包含小写字母进阶要求：时间复杂度：O(n3)O(n^3)O(n3)，空间复杂度：O(n)O(n)O(n) 方法一：暴力枚举具体做法：遍历s1每个字符作为起点，然后遍历以其为起点的每个长度的长度，即暴力枚举字符串s1的所有...

C++ 字符串动态规划

2021-10-30

0 381

题解 | #字符串通配符# 来自专栏

题目的主要信息：实现如下2个通配符： *：匹配0个或以上的字符？：匹配1个字符注：能被*和?匹配的字符仅由英文字母和数字0到9组成，输入却不止这两种匹配不区分大小写方法一：递归具体做法：可以在匹配部分过后，将通配符和字符串的剩余部分进入递归继续判断是否可以完成匹配。首...

C++ 递归动态规划字符串

2021-10-29

2 495

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

题目的主要信息：查找两个字符串a,b中的最长公共子串若有多个，输出在较短串中最先出现的那个进阶要求：时间复杂度：O(n3)O(n^3)O(n3)，空间复杂度：O(n)O(n)O(n) 方法一：暴力枚举具体做法：我们可以先比较两个字符串的长度，然后将s1设置为较短的字符串，s2设置为较长...

C++ 动态规划字符串

2021-10-29

12 929

题解 | #小红的树# 来自专栏

题目的主要信息：没有回路的无向连通图，可以看成树，根结点为1 其中一部分结点染成了红色之后有qqq次询问，每次询问以该结点作为根的子树有多少红色结点具体做法：根据输入的父节点，构建树的邻接表。然后用字符串记录输入的染色信息，再通过dfs构建，对树进行染色，构建dp数组。其中dp[i]d...

C++ 动态规划递归 dfs

2021-10-27

2 662

题解 | #放苹果# 来自专栏

题目的主要信息：把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放共有多少种不同的分法，不区分顺序方法一：递归具体做法：因为不区分顺序，所以只考虑苹果分了几份，每份多少个，很容易知道当苹果为0个的时候或者盘子只有1个的时候，只有1种分法。那这个问题子问题就是苹果更少或者盘子更少...

C++ 递归动态规划

2021-10-27

17 597

题解 | #合并回文子串# 来自专栏

题目的主要信息：两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变需求出所有可能的串C中的最长回文子串的长度具体做法：这是一个区间DP问题。我们用dp[l1][r1][l2][r2]dp[l1][r1][l2][r2]dp[l1][r1][l2][r2]表示字符串A在区...

C++ 动态规划

2021-10-26

0 649

题解 | #称砝码# 来自专栏

题目的主要信息：现有一组砝码，重量互不相等，分别为m1m_1m1,m2m_2m2,m3m_3m3 … mnm_nmn 每种砝码对应的数量为x1x_1x1,x2x_2x2,x3x_3x3 ...xnx_nxn 现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量 ...

C++ 动态规划集合

2021-10-21

48 3548