Let us discuss Longest Increasing Subsequence (LIS) problem as an example problem that can be solved using Dynamic Programming.
The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80
} is 6 and LIS is {10, 22, 33, 50, 60, 80}.
Optimal Substructure:
Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as.
L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
To get LIS of a given array, we need to return max(L(i)) where 0 < i < n
So the LIS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.
Overlapping Subproblems:
Following is simple recursive implementation of the LIS problem. The implementation simply follows the recursive structure mentioned above. The value of lis ending with every element is returned using max_ending_here. The overall lis is returned using pointer
to a variable max.
package DP;
import java.util.Arrays;
// 最长递增子序列-Longest Increasing Subsequence
/**
Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that
arr[i] is part of LIS and arr[i] is the last element in LIS
L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
To get LIS of a given array, we need to return max(L(i)) where 0 < i < n
http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
*/
public class LIS {
public static void main(String[] args) {
int[] A = {10, 22, 9, 33, 21, 50, 41, 60};
System.out.println(lis(A));
System.out.println(lis(A, A.length));
}
/*
A Naive recursive implementation of LIS problem
To make use of recursive calls, this function must return two things:
1) Length of LIS ending with element arr[n-1]. We use max_ending_here
for this purpose
2) Overall maximum as the LIS may end with an element before arr[n-1]
max_ref is used this purpose.
The value of LIS of full array of size n is stored in *max_ref which is our final result
*/
public static int _lis(int arr[], int n, int[] maxRef){
if(n == 1){ /* Base case */
return 1;
}
int res, maxEndingHere = 1; // length of LIS ending with arr[n-1]
/* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If
arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs
to be updated, then update it */
for(int i=1; i<n; i++){
res = _lis(arr, i, maxRef);
if(arr[i-1] < arr[n-1] && res+1>maxEndingHere){
maxEndingHere = res + 1;
}
}
// Compare max_ending_here with the overall max. And update the
// overall max if needed
if(maxRef[0] < maxEndingHere){
maxRef[0] = maxEndingHere;
}
// Return length of LIS ending with arr[n-1]
return maxEndingHere;
}
public static int lis(int arr[], int n){
int[] max = {1};
_lis(arr, n, max);
return max[0];
}
//==========================================
// Naive O(n2) DP solution
// 看A[i]能接在哪些数字后面
public static int lis(int[] A){
int[] dp = new int[A.length]; // 对每一个元素存储它的lis
Arrays.fill(dp, 1); // 初始化,每个数字本身就是长度为1的lis
int max = Integer.MIN_VALUE;
// 对每一个数字求其LIS
for(int i=1; i<A.length; i++){
// 找出A[i]能接在哪些数字后面,
// 如果可以接,找出接完后长度最大那个
for(int j=0; j<i; j++){
if(A[j]<A[i]){ // 只有符合递增规律的才能接
// 找出接完后长度最大那个
dp[i] = Math.max(dp[i], dp[j]+1);
max = Math.max(max, dp[i]);
}
}
}
return max;
}
}
http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
分享到:
相关推荐
最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的...
2. 对于数组中的每个元素 `nums[i]`,我们遍历之前的元素 `nums[j]`,如果 `nums[i]` 大于 `nums[j]`,则 `dp[i] = max(dp[i], dp[j] + 1)`,即以 `nums[i]` 结尾的最长上升子序列的长度为之前所有比 `nums[i]` 小的...
输入序列,求最长上升子序列的长度,算法复杂度nlgn
我写的LIS算法,有两种思路,程序全在这个cpp文件中,可以运行
在LIS问题中,我们可以定义一个数组dp,其中dp[i]表示以数组中第i个元素为结尾的最长上升子序列的长度。初始化时,每个元素自身都构成一个长度为1的上升子序列,因此dp[i]至少为1。 接下来,我们遍历数组中的每个...
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 Visual Studio 2012 项目包 使用4种不同的方法实现最长递增子序列
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
使用动态规划思想求出最长单调递增子序列(LIS),时间复杂度为O(n log k)
下面小编就为大家带来一篇LIS 最长递增子序列 Java的简单实现。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
##算法最长递增子序列时间复杂度O(nlogn)##接口JAVA swing ##功能更改输入字符串的长度随机生成输入字符串标记输入字符串中最长的递增子序列
单片机驱动LIS3DH,很详细的源码文档。
还提供了一个用于区分列表的功能,该功能利用了 LIS 算法。
ST官方网站提供的驱动和实例代码,使用时需要在读写寄存器接口增加硬件驱动
陀螺仪LIS3DH驱动程序,没有工程,LIS3DH驱动程序,使用都可以根据例程来写,只要再写两条程序就行了,在驱动程序中的读与写程序。
1. 定义状态: 2. 状态转移方程: 3. 初始化: 4. 输出: 5. 空间优化: 1 .定义新状态: 2. 状态转移方程: 3. 初始化: 4. 输出:
这时候B[1..2] = 1, 5,Len=2再来,d[4] = 3,它正好加在1,5之间,放在1的位置显然不合适,因为1小于3,长度为1的LIS最小末尾应该是
LIS2DH12TR,LIS3DH应用笔记,lis3dhrt,3axis
LIS3DSH的驱动库(已生成BIN文件)和官方英文数据手册资料
本资源为ST公司官方LIS3DH 、LIS3DSH驱动及例子。资源解压后的driver文件夹可直接在你的工程中应用:The driver is platform independent, you need only to complete the two functions for write and read from ...
LIS3DH 资料_完整例程_手册_电路等