Tag: 动态编程

最长的子序列，动态编程

我有以下问题： 找到给定序列/数组的增长最长的子序列。 换句话说，找到数组的子序列，其中子序列的元素严格按顺序递增，并且子序列尽可能长。 该子序列不一定是连续的或唯一的。 在这种情况下，我们只关心最长的增长子序列的长度。 示例： 输入：[0,8,4,12,2,10,6,14,1,9,5,13,​​3,11,7,15]输出：6序列：[0,2,6,9， 13,15]或[0,4,6,9,11,15]或[0,4,6,9,13,15] 这是一个DP问题，我在记忆步骤中确实遇到了一些问题。 这是我的代码： public int lis(final List a) { return maxIncreasing(0, Integer.MIN_VALUE, a); } HashMap memo = new HashMap(); private int maxIncreasing(int index, int lastElt, final List a) { if(memo.containsKey(index)) return memo.get(index); // end? if(index >= a.size()) return 0; int weTake = Integer.MIN_VALUE; // can we take it? […]

属性文件未使用Apache Commons Configuration反映修改的更改

我正在尝试探索Apache commons配置以动态加载属性文件并在文件中进行修改并保存。 我为此写了一个演示代码。 代码片段 package ABC; import org.apache.commons.configuration.ConfigurationException; import org.apache.commons.configuration.PropertiesConfiguration; import org.apache.commons.configuration.reloading.FileChangedReloadingStrategy; public class Prop { public static void main(String[] args) { try { URL propertiesURL = Prop.class.getResource(“/d1.properties”); if (propertiesURL == null) { System.out.println(“null”); } String absolutePath=propertiesURL.getPath(); PropertiesConfiguration pc = new PropertiesConfiguration(absolutePath); pc.setReloadingStrategy(new FileChangedReloadingStrategy()); String s=(String)pc.getProperty(“key_account_sales”); System.out.println(“s is ” + s); pc.setAutoSave(true); pc.setProperty(“key_account_sales”, “Dummy”); pc.save(); […]

如何查找子arrays在Java中的2D数组中是否有特定的总和？

我试图通过比较源图像和图案图像中存在的像素的平均颜色来解决图像匹配问题。 我已经将这个问题简化为子数组求和问题，但无法找到解决问题的方法。 假设我有一个带有所有正整数的二维arraysARR。 我有一个数字x（这是小图案图像中存在的像素颜色的平均值）。 我只需要在ARR中找到具有精确和x的任何子arrays。 我发现了一个类似的问题，可以通过动态编程来解决。 http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/ 但是，这谈到了找到一个具有最大总和而不是已经给出的总和的子arrays。 所以，如果这是给定的数组。 3 4 8 9 3 2 10 4 2 1 8 1 4 8 0 3 5 2 12 3 8 1 1 2 2 如果给定的总和是19，那么它应该返回此窗口 3 4 8 9 3 2 10 4 2 1 8 1 4 8 0 3 5 2 12 3 […]

给定一个整数0-9的存量，在我用完一些整数之前，我可以写的最后一个数字是多少？

正如标题所说，给定0-9的整数，在我用完一些整数之前，我能写的最后一个数字是多少？ 因此，如果我给了一个库存，比如从0到9的每个数字为10，那么在我用完一些数字之前，我可以写的最后一个数字是多少。 例如，股票为2我可以写数字1 … 10： 1 2 3 4 5 6 7 8 9 10 在这一点上我的股票是0，我不能写11.还要注意，如果给我一个3的股票，我仍然只能写1 … 10，因为11将花费我2个，这将将我的股票留给-1。 到目前为止我得到了什么： public class Numbers { public static int numbers(int stock) { int[] t = new int[10]; for (int k = 1; ; k++) { int x = k; while (x > 0) { if (t[x % 10] […]

算法 – O（n）中二进制搜索树的每两个节点之间的距离之和？

问题是找出BinarySearchTree的每两个节点之间的距离总和，假设每个父子对由单位距离分开。 每次插入后都要计算。 例如： ->first node is inserted.. (root) total sum=0; ->left and right node are inserted (root) / \ (left) (right) total sum = distance(root,left)+distance(root,right)+distance(left,right); = 1 + 1 + 2 = 4 and so on….. 我提出的解决方案： 蛮力。 脚步： 执行DFS并跟踪所有节点： O(n) 。 选择每两个节点并使用最低公共祖先方法计算： O(nC2)_times_O(log(n))=O(n2log(n))之间的距离并将它们相加。 总体复杂性： -O(n2log(n)) 。 O(nlog(n)) 。 脚步：- 在插入之前执行DFS并跟踪所有节点： O(n) 。 计算插入节点与之间的距离： O(nlog(n)) […]

一步的最小步骤

问题陈述 ： 在正整数上，您可以执行以下3个步骤中的任何一个。 从中减去1。 （n = n – 1） 如果它可被2整除，则除以2.（如果n％2 == 0，则n = n / 2） 如果它可被3整除，则除以3.（如果n％3 == 0，则n = n / 3）。 现在问题是，给定正整数n，找到将n取为1的最小步数 例如： 对于n = 1，输出：0 对于n = 4，输出：2（4/2 = 2/2 = 1） 对于n = 7，输出：3（7 -1 = 6/3 = 2/2 = 1） 我知道使用动态编程并具有整数数组的解决方案。 这是代码。 public int bottomup(int n) { //here i am […]

使用动态编程找到子集和的解决方案

我想做的事 我想找到一个与目标T相加的数组的子集。 我还想使用动态编程方法（以及自下而上的解决方案）来做到这一点。 我现在有什么 目前我只找到一种方法来查看是否在所有大小为N子集中，是否存在至少一个具有所需总和的子集。 见下面的代码。 public boolean solve(int[] numbers, int target) { //Safeguard against invalid parameters if ((target < 0) || (sum(numbers) < target)){ return false; } boolean [][] table = new boolean [target + 1] [numbers.length + 1] ; for (int i = 0; i <= numbers.length; ++i) { table[0][i] = true; } […]

Java编程：楼梯动态编程示例

一个人正在爬楼梯，有n个台阶，可以一次走1步，2步或3步。 现在编写一个程序来计算孩子跑楼梯的可能方式。 给出的代码如下 public static int countDP(int n, int[] map) { if (n-1) return map[n]; else { map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); return map[n]; } } 我知道C和C ++，而不是JAVA。 这是来自Cracking the Coding的采访书。 任何人都可以解释一下 为什么以及如何在这里使用function图？ 这里的地图是arrays吗？ 我没有看到任何行保存输入到地图数组，但它会如何返回一些东西？ 有人知道这段代码的C ++或C版本吗？ 很难理解这段代码。 也许不是因为JAVA语法，而是动态编程的隐式结构。 这个算法的时间复杂度是多少？ 它应该小于O（3 ^ n）？ 我将不胜感激。 多谢你们

两个球员网格遍历游戏

给定一个M * N网格和两个玩家p1和p2在网格上的位置。 有n个球放在网格上的不同位置。 设这些球的位置为B(1), B(2), B(3) …, B(n) 。 我们需要计算选择所有球所需的最小曼哈顿距离 。 如果i < j则应按升序选择球，即如果在B(j)之前选择B(j) 。 请考虑以下示例案例： p1 = (1, 1) p2 = (3, 4)让我们考虑球的位置为B(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5) 输出将为5因为p1将首先选择B(1), B(2), B(3)并且p1将选择B(4) 我的方法 我做了一个贪婪的 方法并计算了给定球B(i)的p1和p2距离（从i = 1 to n ）并且将最小值加到输出并相应地更新了玩家的位置。 但是这种方法在许多测试用例中都失败了。 PS：在我过去的一次采访中提出了这个问题， O(n)解决了这个问题的预期。 编辑：更多的测试用例可以是 […]

子集和的动态编程方法

给出以下输入 10 4 3 5 5 7 哪里 10 = Total Score 4 = 4 players 3 = Score by player 1 5 = Score by player 2 5 = Score by player 3 7 = Score by player 4 我打印的玩家组合得分加总，所以输出可以是1 4因为玩家1 +玩家4得分= 3 + 7 – > 10或输出可以是2 3因为玩家2 +玩家3得分= 5 + 5 – […]