摸鱼学大师

题解

未归档(8)

/ 注册

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

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

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

C++ 动态规划

2021-10-10

2 476

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

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

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

2021-10-08

0 378

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

题目的主要信息：要从一个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 343

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

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

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

2021-09-30

7 542

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

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

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

2021-09-14

1 612

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

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

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

2021-09-03

0 660

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

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

动态规划数组

2021-08-31

0 521

题解 | #Fibonacci sSum# 来自专栏

思路：题目的主要信息：斐波那契数列，其中求方法一：暴力解法（超时）具体做法：使用动态规划求斐波那契数列前n项的值，然后三个循环按照公式相加。 class Solution { public: int mod = 1e9 + 7; int getSum(int n) { ...

矩阵快速幂斐波那契数列动态规划数列求和

2021-08-26

0 554

题解 | #好多牛牛# 来自专栏

思路：题目的主要信息：从字符串s的子序列中找到等于"niuniu"的子序列数子序列即原串的删去任意个字符（包括0和全部）字符串s长度默认不小于10，结果需取模1e9+7 方法一：动态规划具体做法：我们用表示以i-1为结尾的s子序列中出现以j-1为结尾的字符串t的个数，...

动态规划字符串子序列

2021-08-11

0 529

题解 | #平衡的选择题# 来自专栏

思路：题目的主要信息：选择题答案有15种情况：A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCDA,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD 对于每道题，要使前道题，A与C的相差不超过1，B与D想抄不超过...

动态规划平衡滚动数组

2021-08-11

0 447