不会做题的小菜鸡

题解

/ 注册

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

题解 | #最少素数拆分# 来自专栏

思路题目分析题目要求我们在给定正整数N的情况下，求出用素数相加得到N，所需要的最少的素数个数根据哥德巴赫猜想，大于2的偶数都可以拆分成两个素数之和（暂时未找到反例），所以我们可以直接用这个猜想。本题的关键在于，对于一个数字N，看似要找的素数的个数可以有很多个，但是经过数学推理，其实这个最...

递归动态规划数学

2021-08-21

0 591

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

本题是动态规划的一道典型题目，也被收录在《算法导论》中当做动态规划章节的学习例题，是非常重要的一道题，可以很好锻炼到动态规划的思路模式。思路题目分析题目给出了两个字符串，要求我们从这两个字符串中，找出最长的公共部分组成子串需要注意的是，最终的子串中的元素必须在两个初始字符串中都出现而...

动态规划

2021-08-06

0 522

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

思路题目分析题目首先给出了一个数组，要求在这个数组中找出仍然保留相对前后顺序，并且成递增规律的最长的子数组我们首先需要有一个概念，这种求序列最长最短子序列的问题可以考虑动态规划，因为通常情况下都符合动态规划的子问题结构的特征，本题就可以从这个点入手。处理最长递增子序列问题是典型的动...

动态规划二分

2021-07-21

0 609

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

思路动态规划（k棋n层）：dp(k,n)表示有k个棋子n层楼需要尝试的次数，题干要求的是dp(k,n)的结果，我们现在选择在第i层扔棋子如果棋子碎了，则剩下k-1个棋子，此时找的楼层更新为i-1（低楼层），即应该继续尝试的次数为dp(k-1,i-1) 如果棋子没碎，则剩下k个棋子，此时要找...

动态规划二分法

2021-07-18

15 2119

题解 | #子数组最大乘积# 来自专栏

思路此题是一类动态规划问题，具有重叠子问题和最优子结构的特点，通过找到状态转移方程式来解决问题方法一：动态规划我们可以定义一个动态规划数组dp[i]，其表示的是从索引0到索引i位置为止，这一段区间存在的子数组的最大乘积保存在dp[i]中，因此对于一个n长的数组，最终返回结果为max(dp[0...

动态规划

2021-07-16

4 940

题解 | #丑数# 来自专栏

思路根据题中定义，我们了解到丑数都是可以拆分为 2^x*3^y*5^z 的数字，因此思路集中在解决质因数的分解问题上，如何巧妙地利用质因数会衍生出不同的思路暴力解法（超时）：直接判断每一个自然数是否是符合丑数的质因数分解规律最小堆解法：维护一个丑数最小堆，每次从堆顶取出当前最小值i，并再将2...

最小堆动态规划

2021-07-15

5 1071