摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #跳台阶扩展问题# 来自专栏

思路：题目的主要信息：对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数（与斐波那契数列不一样） n为正整数，求青蛙跳上n级台阶的方案数方法一：暴力解法具体做法：对于n个阶梯，如果青蛙第一次选择跳1阶，那么它有还剩下n-1阶，如果选择跳2阶，那么它还剩下n-2阶以此类推，后面剩...

递归动态规划跳台阶数学

2021-07-27

0 395

题解 | #斐波那契数列# 来自专栏

思路：题目的主要信息：斐波那契数列每项的公式为:，从0开始，，求出斐波那契数列的第n项 n最大不超过39，结果不会超出int的范围，不用考虑long long 方法一：递归具体做法：根据公式，每次返回，结束递归的点就是1或者0 class Solution { public: in...

斐波那契数列动态规划递归记忆化

2021-07-27

0 0

题解 | #二叉树的个数# 来自专栏

思路：题目的主要信息：一棵树树的结点数为n 其中序遍历递增但是题中并没有提到结点中的数据如何，只要数据任意组合的话，任何二叉树都可以有一个中序递增序列，因此这道题就化为结点数为n的二叉树有多少种，这就变成了算法中的卡特兰数（Catalan数）的问题：如果没有结点，只有空树一种形态，则 ...

动态规划卡兰特数二叉树中序遍历大整数

2021-07-27

1 594

题解 | #几步可以从头跳到尾# 来自专栏

思路：题目的主要信息： n长度的数组，每个元素表示从该数下标位置最多可往后跳跃多少个从1开始，无0的情况方法一：动态规划（可能会超时）题目要求的是找出从1跳到n最快的路径，即所需步数最短，我们可以想到遍历所有的路径，从中找出步数最短的路径。具体做法：我们可以用dp[i]表示第i个元素到最后...

动态规划贪心数组

2021-07-27

0 956

题解 | #01背包# 来自专栏

题目的主要信息：背包体积固定为V，从所有物品中选择几件物品，加起来体积不超过V，使加起来质量最大。所有数据大于0，无特殊情况方法一：递归（超时）递归是一种分治法，我们可以如下考虑： xix_ixi为1或0，表示对于物品iii取或者不取，viv_ivi表示物品iii的体积，wiw_i...

01背包动态规划递归

2021-07-26

3 980

题解 | #不相邻最大子序列和# 来自专栏

思路：题目的主要信息：在数组中，选取一组序列，使和最大选取的数中，位置不能相邻可以不选或是选一个数方法一：递归（超时）具体做法：对于n个元素的数组，如果最后一个数字被选择了，则前一个数字必不会被选，那就是n-2的结果加上最后一个数字，如果最后一个数字没有被选择，则是n-1的结果，选取其...

动态规划递归数组子序列

2021-07-25

0 549

题解 | #把数字翻译成字符串# 来自专栏

思路：题目的主要信息：字母到数字分别为1-26映射，没有0 输入的数字是字符串，故非常大，超过了long long的表示范围但凡出现11-19，21-26的就可能出现两种译码结果求总后的译码结果种类方法一：递归（超时）具体做法：遍历字符串，每到一位，可以查看它是可以跨越两步还是只能...

动态规划字符串递归

2021-07-21

0 697

题解 | #最长公共子序列-II# 来自专栏

思路：题目的主要信息：仅存在一个最长公共子序列，不需要去重最长公共子序列为空需要返回"-1"，而不是空序列，最后要变换我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度，若是i与j相等，则该问题可以变成1+dp[i][j]，即最长公...

动态规划字符串公共子序列递归栈

2021-07-18

1 1320

题解 | #最长递增子序列# 来自专栏

思路：先找最长递增子序列长度再根据长度逆向得到序列（逆向的原因是字典序更小，若是小值跑到后面去的情况，同样长度大值跑后面只会增加子序列长度）要找到最长的递增子序列长度，常用方法是动态规划，dp[i]表示到元素i结尾时，最长的子序列的长度，初始化全部为1。方法一：暴力动态规划（超时）具...

动态规划二分法子序列数组

2021-07-17

1 1184

题解 | #丢棋子问题# 来自专栏

思路：题目中给到的信息：第0层不会碎某层没有碎，下面的必然不会碎；某层碎了，上面的必然碎要求最坏情况方法一：暴力递归（超时）设count(n,k)计算的是n层楼时且有k个棋子，在最差的情况下需要仍的最少次数。当k=0时，没有棋子，不用仍当n=0时，棋子肯定不会碎，所以count...

丢棋子动态规划递归

2021-07-16

1 668