-
0 votesanswersviews
动态编程：通过网格找到障碍物的最短路径
我'm trying to solve the following problem from Skiena'的算法设计手册： 8-16考虑一个城市，其街道由X x Y网格定义 . 我们感兴趣的是从网格的左上角走到右下角 . 不幸的是，这个城市有不好的社区，我们不想走路的交叉点 . 我们给出一个X x Y矩阵BAD，其中BAD [i，j] =“是”当且仅当街道i和j之间的交叉点在附近避免 . （... -
6 votesanswersviews
这个问题NP难吗？
我正在尝试为这个问题提出一个合理的算法： 假设你有一堆球 . 每个球至少有一种颜色，但也可以是多色的 . 每个球上都有一个数字 . 还有一堆盒子，每个盒子只有一种颜色 . 目标是最大化框中球的数字总和，唯一的规则是： 为了将球放在一个盒子里，它必须至少有一个盒子的颜色 你每个盒子里只能放一个球 . 例如，您可以将蓝色和绿色球放入蓝色框或绿色框中，但不能放入红色框中 . 我已经提出了一些... -
-1 votesanswersviews
最小数量的硬币进行更改
我试图打印最小数量的硬币进行更改，如果不可能打印-1 在这个代码变量int [] c（coins数组）中有面额我可以用来得出总和 . int total总计我需要拿出使用硬币（无限供应） public static int mincoinDP(int[] c, int total) { int[][] a = new int[c.length + 1][total + 1]; ... -
0 votesanswersviews
具有重复键的BST数量
如果n个顶点的键不同于Catalan number给出的BST的数量 . 但是，如果某些元素重复，我们如何计算BST的数量？ 我天真的想法，如果我们在n中有k个相等的元素，那么我们应该在k上划分加泰罗尼亚数字！（k个元素的排列） . 但是如果我们在最简单的例子（BST构建在[1,1,1]上）检查它，我们就会意识到这是错误的想法 . 那么，当我们计算BST的数量时，我们应该如何考虑重复的密钥？ Wh... -
0 votesanswersviews
动态编程 - 达到给定目标的组合数
这是一个基本的动态编程问题 - 得分组合数 . 我知道这个问题的自下而上的方法很有效 . 但是，我无法为此问题寻找自上而下的解决方案方法 . 缓存递归部分给了我们超过必要的组合（其中排序/分数序列也是一个因素，因此，为了避免它，我们需要提供一个约束来使序列单调增加 . 这是相同的递归方法.Dynamic Programming - Number of distinct combinations t... -
1 votesanswersviews
找到从n-ary树的根到叶的最大路径，而不包括总和中两个相邻节点的值
我最近接受了采访，并被问到以下问题 . 给定n-ary树，找到从根到叶的最大路径，使得最大路径不包含来自任何两个相邻节点的值 . （另一个编辑：节点只有正值 . ） （从注释编辑：相邻节点意味着共享直接边缘的节点 . 因为它是树，它意味着父子 . 所以如果我包括父，我不能包括子，反之亦然 . ） 例如： 5 / \ 8 10 / \ / ... -
3 votesanswersviews
仅使用超过阈值的指定面额的硬币可以获得的最小金额
换句话说，给定一组n个正整数 A 和一个阈值 B ，我想找到最小的 C ，这样： C > B C = A[1] * k[1] + A[2] * k[2] + ... + A[n] * k[n] ， k[i] 是整数> = 0 作为示例 A = { 6, 11, 16 } 然后我们可以获得的值是： { 0, 6, 11, 12, 16, 17, 18, 22, 23, 24,... -
4 votesanswersviews
检查是否可以进行分词
这是this response以及用户发布的伪代码算法的后续问题 . 我没有需要实际拆分字符串 . 这是相关问题的回复： 设S [1..length（w）]是一个带有布尔条目的表 . 如果可以拆分单词w [1..i]，则S [i]为真 . 然后设置S [1] = isWord（w [1]）并且对于i = 2到长度（w），计算S [i] =（isWord [w [1..i]或者对于{2..i中的任... -
1 votesanswersviews
如何获得动态CRM在线解决方案的代码
我是Dynamics CRM的新手 . 我的情况是下一个：我们有一个Dynamics CRM online 2016，其中包含第三方创建的一些解决方案，我需要提供一个解决方案的完整代码，我需要查看所有插件，工作流和Javascript文件的代码解决方案有 . 我尝试在Visual Studio中创建一个新的Dynamics CRM项目，然后选择“用于Dynamics CRM的新Visual Stu... -
92 votesanswersviews
想要了解动态编程的人的一个简单示例[关闭]
我正在为想要学习动态编程的人寻找一个易于理解的例子 . There are nice answers here about what is dynamic programming . 斐波那契序列是一个很好的例子，但它太小而不能划伤表面 . 它看起来是一个很好的主题，虽然我尚未参加算法课程，但希望它在我的 Spring 季名单上 . -
189 votesanswersviews
如何使用动态编程确定增长最长的子序列？
我有一组整数 . 我想使用动态编程找到该集合的longest increasing subsequence . -
106 votesanswersviews
分治算法与动态规划的区别
Divide和Conquer算法和动态规划算法有什么区别？这两个术语有何不同？我不明白他们之间的区别 . 请举一个简单的例子来解释两者之间的差异以及它们看起来相似的基础 . -
2 votesanswersviews
这种文本理由的动态编程解决方案是否只是暴力？
我无法理解麻省理工学院开放课件讲座here中规定的文本对齐问题的动态编程解决方案 . 该讲座的一些注释是here，而笔记的第3页就是我所指的 . 我认为动态编程意味着你会记住一些计算，这样你就不需要重新计算，从而节省你的时间，但是在演讲中给出的算法中，我没有看到任何使用memoization，只是一大堆深度递归调用，即主要功能是这样的： DP[i] = min(badness (i, j) + D... -
4 votesanswersviews
在字符串中有效地查找给定的子序列，最大化连续字符的数量
长问题描述 模糊字符串匹配器实用程序（如fzf或CtrlP）会过滤一个字符串列表，其中包含给定搜索字符串作为子序列的字符串 . 例如，考虑用户想要在文件列表中搜索特定照片 . 要查找文件 /home/user/photos/2016/pyongyang_photo1.png 输入 ph2016png 就足够了，因为此搜索字符串是此文件名的子序列 . （请注意，这不是LCS . 整个搜索字符串必... -
1 votesanswersviews
动态编程与记忆耗时比蛮力方法更长
我最初使用蛮力解决了这个challenge并且它被接受了 . 我试图利用memoization动态编程来减少 O(2^n) 的时间复杂度 . 使用memoization的动态编程比蛮力方法花费的时间更长，并且我收到超出时间限制的错误消息 . 蛮力方法代码 . public class Dummy { private int answer = 0; private int numbe... -
1 votesanswersviews
深入理解算法设计技术
“为给定的应用程序设计正确的算法是一项艰巨的任务 . 它需要一个重大的创造性行为，解决问题并从以太中解决问题 . 这比采取其他人的想法并修改它或将其调整为更难 . 让它变得更好 . 你可以在算法设计中做出的选择空间是巨大的，足以让你有足够的自由来悬挂自己“ . 我研究了几种基本的算法，如分而治之，动态编程，贪婪，回溯等 . 但是，当我遇到某些编程问题时，我总是无法认识到适用的原则 . 我想掌握算法... -
2 votesanswersviews
如何使用mPDF和PHP防止PDF格式的表格大小调整？
我有一些表单数据，提交后会生成PDF . 问题是PDF格式的表格大小 . 如果我的表单中的某些字符串太长，则会错误地生成PDF . 这是因为表格 . 它们具有静态大小，因此如果字符串太长，则表格不能容纳它 . 我使用mPDF库 . 如何根据字符串的长度使这个表的大小动态变化，以便它们的大小发生变化？ 如果字符串最长，那么表格的宽度会减小 . 我想如果字符串比表的宽度最长那么应该在下一行写出并且表的... -
2 votesanswersviews
计算给定路径成本下的最大利润
给出了根图 . 这里，节点是“家”，包含一些有 Value 的项目 . 给出入口节点，即图的根 . 还给出了从一个节点移动到另一个节点的成本，即Egde权重 . Question - 您必须收集最大的贵重物品，总成本不应超过给定的成本 . Contraint - 1.没有循环 . 2.我们也可以使用相邻矩阵 . （顶点总数最多为1000） . Example Edges given with ... -
0 votesanswersviews
O（n ^ 2）算法在去除顶点后保留最短路径
如果我想构造一个O（n ^ 2）算法，该算法在移除顶点后保留图形的最短路径距离，我应该使用动态编程来处理这个问题，并且函数存储有关每个双数组框中最短路径的信息吗？ 例如，我有一个图G，我拿出一个顶点，然后得到新的图G2 . 我希望G2的所有顶点之间的最短距离等于原始G的最短距离 -
1 votesanswersviews
动态编程和Dijkstra
我正在阅读以下问题陈述，意在通过动态编程解决： 给定无向图G，其具有N（1 <N <= 1000）个顶点和正权重 . 找到从顶点1到顶点N的最短路径，或说明此路径不存在 . 提示：在每个步骤中，在尚未检查的顶点和找到顶点1的路径的顶点中，取一个具有最短路径的顶点，从顶点1到它，但仍然找到 . 我相信算法应该是这样的 S = starting point N = ending poi... -
0 votesanswersviews
动态编程的最短路径
我不想要这个问题的答案，我只需要朝着正确的方向轻推 . 给定无向图G，其具有N（1 <N <= 1000）个顶点和正权重 . 找到从顶点1到顶点N的最短路径，或说明此路径不存在 . 提示：在每个步骤中，在尚未检查的顶点和找到顶点1的路径的顶点中，取一个具有最短路径的顶点，从顶点1到它，但仍然找到 . 首先，我必须定义一个州 . 这就是我说的： 状态是顶点i的解，其中i <=... -
1 votesanswersviews
图中的最短路径
给定无向图G，其具有N（1 <N≤1000）个顶点和正权重 . 找到从顶点1到顶点N的最短路径，或说明此路径不存在 . 提示：在每个步骤中，在尚未检查的顶点和找到顶点1的路径的顶点中，取一个具有最短路径的顶点，从顶点1到它，但仍然找到 . 我在topcoder上发现了这个问题，我认为应该使用Dijkstra的算法，但是帖子是关于动态编程的，而Dijkstra是一个贪婪的算法 . 谁能告诉我解... -
3 votesanswersviews
背包但确切的重量
是否有算法来确定具有精确重量W的背包？即这就像正常的0/1背包问题，n个项目各有权重w_i和值v_i . 最大化所有项目的 Value ，但是 total weight of the items in the knapsack need to have exactly weight W ！ 我知道“普通”0/1背包算法，但这也可以返回一个重量更轻但 Value 更高的背包 . 我想找到最高值但确切... -
2 votesanswersviews
将一组2n个整数划分为n个整数的两个子集，其总和为正
给定一组2n个整数，是否可以在n个整数的两个子集中找到一个分区，每个子集的总和为正 . 我的想法：我们表示集合v [1]，...，v [2n]的值 . 如果存在该组的前j个整数的分区分别为k和jk整数的两个子集，则设S [j，k，s1，s2] = 1，使得第一子集总和为s1，第二子集求和到s2 . （s1和s2当然可以是否定的） 我们有以下关系：S [j 1，k，s1，s2] = 1 iff S... -
1 votesanswersviews
子集和问题的有趣变化
一位朋友从工作中向我展示了一个有趣的子集和问题变体： 给定S的正整数，大小为n，以及整数a和K，是否存在包含 exactly a elements 的子集R（集合S），其总和等于K？ 他声称这可以用时间复杂度O（nka）来完成，我无法想出一个能够实现这个运行时间的动态编程算法 . 可以吗？ -
1 votesanswersviews
balancer 分区与背包1/0的复杂性
balancer 分区： . 你有一组n个整数，每个都在0 ... K范围内 . 将这些整数划分为两个子集，以便最小化| S1 - S2 |，其中S1和S2表示两个子集中每个子集中元素的总和 . 背包问题：给定一组具有权重和值的项目，确定要包含在集合中的每个项目的数量，以使总权重小于或等于给定限制，并且总值与可能 . 不能两次使用同一个对象 . 似乎 balancer 分区问题的解决方案是简单... -
1 votesanswersviews
动态编程 - 在数组中查找目标求和方式
我在leetcode中遇到了一个问题，我看了其他使用DP的解决方案，但有一些我无法理解的东西，希望你能给我一些提示 . 问题是：给定一个只包含正整数的非空数组，找到选择其总和等于目标S的一些整数的方法 . 解决方案是： int findTargetSumWays(vector<int>& nums, int S) { int n = nums.size(); ... -
4 votesanswersviews
带负数的子集和
所以我有一个给定的C个n个正整数（c_1，...，c_n） . 任务是找到C的两个子集A和B，其中A仅包含正数，B仅包含C中数字的负数 . 然后，两个子集A和B的总和应总和为数d（d永远是积极的） . 我需要找出是否有两个这样的子集，如果有，它们包含哪些数字 . For example: {3, 5, 6, 13, 24} // d = 12 => solution: true: {5, 1... -
7 votesanswersviews
高效的算法来获取对象中所有项的组合
给定一个带有n个键的数组或对象，我需要找到长度为 x 的所有组合 .鉴于 X 是可变的 . binomial_coefficient(n,x) . 目前我正在使用这个： function combine(items) { var result = []; var f = function(prefix, items) { for (var i = 0; i &... -
1 votesanswersviews
动态编程选择nos的元组（大小T），每个不大于k和和S.
伙计们这是个问题 在锦标赛中，N名球员恰好相互比赛一次 . 每场比赛都会导致任何一名球员获胜 . 没有关系 . 你已经给出了一张记分卡，其中包含了比赛结束时每位球员的得分 . 玩家的得分是玩家在锦标赛中赢得的总游戏数 . 但是，某些玩家的得分可能已从记分卡中删除 . 有多少可能的记分卡与输入记分卡一致？ 输入：第一行包含案例数T.T案例如下 . 每个案例包含第一行的数字N，后面是第二行的N个数字 ...