We have discussed Dynamic Programming solution for Longest Increasing Subsequence problem inthispost and a O(nLogn) solution
inthispost.Following are commonly asked variations of the standardLIS
problem.
1. Building Bridges:Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) … a(n) and n cities on the northern bank with x-coordinates b(1) … b(n). You want to
connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank.
8 1 4 3 5 2 6 7
<---- Cities on the other bank of river---->
--------------------------------------------
<--------------- River--------------->
--------------------------------------------
1 2 3 4 5 6 7 8
<------- Cities on one bank of river------->
Source:Dynamic Programming Practice Problems. The link also has well explained solution for the problem.
2. Maximum Sum Increasing Subsequence:Given an array of n positive integers. Write a program to find the maximum sum subsequence of the given array such that the intgers in the subsequence are sorted in increasing order. For example, if input
is {1, 101, 2, 3, 100, 4, 5}, then output should be {1, 2, 3, 100}. The solution to this problem has been publishedhere.
3. The Longest ChainYou are given pairs of numbers. In a pair, the first number is smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d), the second set can follow the first set if b < c. So you can form a
long chain in the similar fashion. Find the longest chain which can be formed. The solution to this problem has been publishedhere.
4. Box StackingYou are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack
a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple
instances of the same type of box.
Source:Dynamic Programming Practice Problems. The link also has well explained solution for the problem.
对于二维的问题,先把一维固定住(排序),在用动态规划处理剩下一维。
package DP;
import java.util.Arrays;
import java.util.Comparator;
public class BuildingBridges {
public static void main(String[] args) {
Pair[] A = new Pair[7];
A[0] = new Pair(22,4);
A[1] = new Pair(2,6);
A[2] = new Pair(10,3);
A[3] = new Pair(15,12);
A[4] = new Pair(9,8);
A[5] = new Pair(17,17);
A[6] = new Pair(4,2);
System.out.println(lis(A));
}
public static int lis(Pair[] A){
Arrays.sort(A, new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
return o1.x - o2.x;
}
});
int n = A.length;
int max = 0;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
if(A[i].y > A[j].y){
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
public static class Pair{
int x, y;
public Pair(int x_, int y_){
x = x_;
y = y_;
}
}
}
http://www.geeksforgeeks.org/dynamic-programming-set-14-variations-of-lis/
http://people.csail.mit.edu/bdean/6.046/dp/
分享到:
相关推荐
LIS------------------------------210种仪器联机设置
LIS3DH-SPI驱动.rar
LIS-------------------------临床检验信息系统LIS工作流程
检验仪器与信息系统的权威标准,200美刀买的,CLSI标准LIS-A1分析仪器与信息系统底层接口规范:Standard Specification for Low-Level Protocol to Transfer Messages Between Clinical Laboratory Instruments and...
ADVIA Centaur CP LIS-Interface-Guide.pdf,检验仪器联机文档,支持双向通讯,希望对LIS开发工程师有用
stm32L0单片机通过iic通讯控制LIS3DH三轴传感器,通过fifo模式读取数据
LIS源码-WORD,代码分享,LIS源码-WORD,代码分享LIS源码-WORD,代码分享LIS源码-WORD,代码分享
LIS3DH 开发板,三轴加速度计LIS3DH开发板的手册,为初学者应用LIS3DH提供借鉴。
LIS3DSH是一款由意法半导体(STMicroelectronics)生产的超低功耗、高性能的三轴线性加速度传感器。它属于“nano”系列,并且带有嵌入式状态机,能够实现自主应用的编程。以下是LIS3DSH的一些主要特性和应用场景: ...
LIS3DH中文数据手册 + 驱动 + 测试Demo
LIS3DSH是一款由意法半导体(STMicroelectronics)生产的超低功耗、高性能的三轴线性加速度传感器。它属于“nano”系列,并且带有嵌入式状态机,能够实现自主应用的编程。以下是LIS3DSH的一些主要特性和应用场景: ...
具體邏輯在第4章介紹。如lis-business-PC等package下。其路徑如下圖所示:其中,com\sinosoft\lis是固定的,pc是某個綫別的模組
三轴加速度计数据手册,详细说明了三轴加速度计的使用方法和寄存器的操作
LIS----document--Laboratory Information System
Enabling Large Intelligent Surfaces with Compressive Sensing and Deep Learning
LIS-5937-Python
迈瑞LIS 接口疑难常见问题解答,包括血常规直方图图像问题等
lidar数据las格式的详细说明(英文).方便了解las格式的具体内容.
单片机驱动LIS3DH,很详细的源码文档。
XX软件科技股份有限公司-LIS系统培训-保全致力于为大家提供学习、参考最实用的资源,对XX软件科技股份有...该文档为XX软件科技股份有限公司-LIS系统培训-保全,是一份很不错的参考资料,具有较高参考价值,感兴趣的...