摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

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

孤帆远影碧空尽

547篇文章 10952人学习

全部文章（共87篇）

题解 | #统计每个月兔子的总数# 来自专栏

题目的主要信息：有一对兔子，从出生后第 3 个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第n个月的兔子对数为多少? 我们有如下计算：月份兔子数（对）第1个月 1对兔子第2个月 1对兔子第3个月 2对兔子（第一对生出第二对）...

C++ 递归动态规划

2021-10-21

25 1669

题解 | #密码截取# 来自专栏

题目的主要信息：输入一个长度不超过2500的字符串找到其中最长的回文子串长度方法一：中心扩散法具体做法：我们可以遍历每个字符串每个位置，都以其为回文子串的中心，或是奇数长度子串的中心（从两边开始找），或是偶数长度的子串中心（以它左边和它一起），分别向两边扩散，只要这个过程中两边字符是相...

C++ 动态规划字符串

2021-10-19

41 1649

题解 | #合唱队# 来自专栏

题目的主要信息：给出nnn个同学的身高，在不改变所有人的相对位置的情况下从中剔除几位，使得剩下的kkk位同学的身高排序是形如：T1<T2<T3<...<Ti>Ti+1>...>TkT_1<T_2<T_3<...<T_i>T_...

C++ 动态规划二分法

2021-10-11

3 473

题解 | #购物单# 来自专栏

题目的主要信息：输入一个NNN和一个mmm，NNN表示现有的钱，mmm表示有mmm件物品，接着输入每件物品的价格、重要度、是否附属等信息对于主件物品可以直接买，对于附件物品需要先购买主件才能购买附件，主件有0-2个附件所有的价格，及金额都是10的整数倍在不超过金额NNN元的情况下，使购买的...

C++ 动态规划

2021-10-10

3 485

题解 | #填数游戏# 来自专栏

题目的主要信息：长为n的连续格子，要在格子里面填上1、2、3、4这四个数字要求同一个偶数出现的次数也是偶数次，即2出现偶数次，4也要出现偶数次求填充的方案种数，要对答案取模1e9+7 方法一：动态规划（超时）具体做法：我们可以用动态规划来表示，建立数组dp，其中： dp[i][0]dp...

C++ 快速幂矩阵快速幂快速乘法动态规划

2021-10-08

0 384

题解 | #走网格# 来自专栏

题目的主要信息：要从一个n∗mn*mn∗m网格的(1,1)(1,1)(1,1)位置走到(n.m)(n.m)(n.m)，每次只能往下或者往右，其中网格中有一块区域不能走不能走的区域，左下角坐标是(x0,y0)(x_0,y_0)(x0,y0)，右下角坐标是(x1,y1)(x_1,y_1)(x1...

C++ 动态规划递归

2021-09-30

0 349

题解 | #跳台阶# 来自专栏

题目的主要信息：一只青蛙一次可以跳上1级台阶，也可以跳上2级，先后次序算不同的方案求该青蛙跳上一个n级的台阶总共有多少种跳法要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(1)O(1)O(1) 方法一：动态规划具体做法：我们用可以考虑第n级台阶，它可以由第n-1级台阶跳1级而来...

C++ 动态规划矩阵快速幂数学

2021-09-30

7 532

题解 | #反复横跳# 来自专栏

题目的主要信息：一张带权无向图，图中任意两点间有且仅有一条路径，这是一棵无向树计算从任意点出发并访问完所有节点经过边的权值之和的最小值分析：首先，如果我们要从一个点到达其他所有点，每条边我们必须经过一次，因为任意两点之间有且仅有一条路径。然后，因为可以到树叶以后再回溯访问，再到另外的枝，...

动态规划图递归 dfs 树的直径

2021-09-14

1 620

题解 | #牛妹的野菜（权值最大的路径）# 来自专栏

思路：题目的主要信息：一个有向无环图，路径是单向从小序号到大序号，每个节点有权值求图中一条权值和最大的路径，并以字符串输出这条路径方法一：动态规划具体做法：我们可以用动态规划的方式来解决。首先利用给出的路径数组构建一个邻接矩阵，我们以weigh数组表示从每个节点开始的最长路径的长度，pa...

空间记忆搜索递归动态规划 dfs 图

2021-09-03

0 671

题解 | #金字塔数组# 来自专栏

思路：题目的主要信息：对于一个数组，如果呈现先递增后递减的趋势，则称之为金字塔数组求连续数组num中的最长金字塔子数组长度，不存在输出0 方法一：动态规划具体做法：我们可以使用最长递增子序列的动态规划法来做这道题。准备两个数组，increase[i]表示到i为止的最长递增子序列长度，dec...

动态规划数组

2021-08-31

0 539