找到 201 篇文章 关于动态规划

加权作业调度

Ankith Reddy
更新于 2020年6月17日 07:53:36

791 次浏览

给定一份不同的工作列表,其中包含每项工作的开始时间、结束时间和利润。我们的任务是找到一个利润最大且没有工作相互重叠的作业子集。在这个算法中,我们使用一个表来存储子问题的结果,并使用子问题的结果,以自底向上的方式解决整个问题。该算法的时间复杂度为 O(n^2),但我们可以通过使用二分查找方法来搜索冲突作业将其更改为 O(n Log n)。输入… 阅读更多

丑数

George John
更新于 2020年6月17日 08:04:29

4K+ 次浏览

丑数是指质因数只有 2、3 或 5 的数字。从 1 到 15,有 11 个丑数 1、2、3、4、5、6、8、9、10、12、15。数字 7、11、13 不是丑数,因为它们是质数。数字 14 不是丑数,因为它的质因数中包含 7。在这个程序中,我们将尝试找到第 n 个丑数。输入和输出输入:输入项数。假设它是 10 输出:第 10 个丑数是 12算法getUglyNumbers(n)输入:项数。输出:找到第 n 个丑数。开始 定义名为… 阅读更多

最短公共超序列

Chandu yadav
更新于 2020年6月17日 08:09:32

192 次浏览

最短公共超序列是一个序列,其中包含两个给定序列的每个元素。换句话说,我们可以说给定的两个字符串都是最短公共超序列的子序列。当两个字符串中没有公共字符时,我们可以简单地将它们连接起来以获得超序列。但是当它们有一些公共字符时,首先我们必须找到最长的字符串,然后添加另一个字符串的额外字符。输入和输出输入:两个字符串。“ABCDEF”和“XYDEF”输出:最短公共超序列的长度。这里的超序列是“ABCDEFXY”。所以长度是… 阅读更多

杆切割

Samual Sam
更新于 2020年6月17日 08:11:06

6K+ 次浏览

给定一根长度为 n 的杆。还提供另一个表,其中包含每种尺寸的不同尺寸和价格。通过切割杆并在市场上出售来确定最高价格。通过在不同位置切割并比较切割杆后的价格来获得最佳价格。设 f(n) 将返回切割长度为 n 的行后可能获得的最大价格。我们可以简单地这样编写函数 f(n)。f(n) := price[i]+f(n – i – 1) 的最大值,其中 i 的范围为 0 到 (n – 1)。输入和输出输入:价格… 阅读更多

分割问题

karthikeya Boyini
更新于 2020年6月17日 07:25:03

1K+ 次浏览

对于这个问题,给定的集合可以这样划分,使得每个子集的和相等。首先,我们必须找到给定集合的和。如果它是偶数,那么就有机会将其分成两个集合。否则,它不能被分割。对于偶数和值,我们将创建一个名为 partTable 的表,现在使用以下条件来解决问题。当数组[0] 到数组[j-1] 的子集的和等于 i 时,partTable[i, j] 为真,否则为假。输入和输出输入:一组整数。{3, 1, 1,… 阅读更多

回文划分

George John
更新于 2020年6月17日 07:22:59

333 次浏览

在这个算法中,输入是一个字符串,当划分的每个子串都是回文时,该字符串的划分就是回文划分。在这个算法中,我们必须找到将给定字符串进行回文划分所需的最小切割次数。输入和输出输入:一个字符串。例如“ababbbabbababa”输出:作为回文的最小切割数。这里需要 3 次切割。回文是:a | babbbab | b | ababa算法minPalPart(str)输入:给定的字符串。输出:从字符串中进行回文划分的最小次数。开始 n := str 的长度 定义大小为 n x n 的切割矩阵和回文矩阵… 阅读更多

朋友配对问题

Ankith Reddy
更新于 2020年6月17日 07:29:15

588 次浏览

在一个群体中,有 n 个朋友。每个人都可以保持单身或与其他一些朋友配对。找到朋友可以保持单身或配对的总方法数。如果一对朋友 p 和 q,那么 (p, q) 或 (q, p) 是相同的。对于一组 n 个朋友,设 f(n) 是他们可以配对或保持单身的次数。那么第 n 个人要么保持单身,要么配对。如果第 n 个人是单身,那么我们对 (n - 1) 个朋友进行递归。如果… 阅读更多

通配符模式匹配

Samual Sam
更新于 2020年6月17日 07:27:53

1K+ 次浏览

对于这个问题,给定一个主字符串和另一个通配符模式。在这个算法中,它将检查通配符模式是否与主文本匹配。通配符模式可能包含字母或“*”或“?”符号。“?”用于匹配单个字符,“*”用于匹配包括空字符在内的字符序列。当字符为“*”时:我们可以忽略星号字符并移动到检查模式中的下一个字符。当下一个字符为“?”时,我们只能忽略文本中的当前字符,并检查… 阅读更多

最优二叉搜索树

karthikeya Boyini
更新于 2020年6月17日 07:32:27

6K+ 次浏览

给定一组按排序顺序排列的整数和另一个数组 freq 用于频率计数。我们的任务是使用这些数据创建一个二叉搜索树,以找到所有搜索的最小成本。创建一个辅助数组 cost[n, n] 来解决和存储子问题的解。成本矩阵将保存数据,以便以自底向上的方式解决问题。输入和输出输入:作为节点的键值和频率。键 = {10, 12, 20} 频率 = {34, 8, 50} 输出:最小成本为 142。这些是从给定值中可能的 BST。对于… 阅读更多

将数字分成 3 部分以找到最大和

Samual Sam
更新于 2020年6月17日 07:33:43

456 次浏览

给定一个数字。我们的任务是将数字通过 n/2、n/3 和 n/4 三次分割,并找到通过将数字分成三部分可以获得的最大和。例如,50 可以分成 {25, 16, 12},现在再次将每个集合 {25, 16, 12} 分成三个部分,依此类推。在完成最多 3 次分割后,我们将计算总和以找到其中的最大值。这个程序可以用递归的方式来解决,但在递归方法中,我们需要多次找到相同的结果,… 阅读更多

广告