一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度。 (讲DP基本都会讲到的一个问题LIS:Longest Increasing Subsequence)
面对这样一个问题,我们首先要定义一个“状态”来代表它的子问题, 并且找到它的解。注意,大部分情况下,某个状态只与它前面出现的状态有关, 而独立于后面的状态。
我们来找一下“状态”和“状态转移方程”。 假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度,其中i<N, 那么上面的问题变成了原问题的一个子问题(问题规模变小了,你可以让i=1,2,3等来分析) 然后我们定义d(i),表示前i个数中以A[i]结尾的最长非降子序列的长度。这个d(i)就是我们要找的状态。 如果我们把d(1)到d(N)都计算出来,那么最终我们要找的答案就是这里面最大的那个。 状态找到了,下一步找出状态转移方程。
为了方便理解我们是如何找到状态转移方程的,我先把下面的例子提到前面来讲。 如果我们要求的这N个数的序列是:
5,3,4,8,6,7
根据上面找到的状态,我们可以得到:(下文的最长非降子序列都用LIS表示)
- 前1个数的LIS长度d(1)=1(序列:5)
- 前2个数的LIS长度d(2)=1(序列:3;3前面没有比3小的)
- 前3个数的LIS长度d(3)=2(序列:3,4;4前面有个比它小的3,所以d(3)=d(2)+1)
- 前4个数的LIS长度d(4)=3(序列:3,4,8;8前面比它小的有3个数,所以 d(4)=max{d(1),d(2),d(3)}+1=3)
OK,如果我们已经求出了d(1)到d(i-1), 那么d(i)可以用下面的状态转移方程得到:
d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]
想要求d(i),就把i前面的各个子序列中, 最后一个数不大于A[i]的序列长度加1,然后取出最大的长度即为d(i)。 当然了,有可能i前面的各个子序列中最后一个数都大于A[i],那么d(i)=1, 即它自身成为一个长度为1的子序列。
分析完了,上图:(第二列表示前i个数中LIS的长度, 第三列表示,LIS中到达当前这个数的上一个数的下标,根据这个可以求出LIS序列)
public int longestIncreasingSubsequence(int[] num) { int[] f = new int[num.length]; Arrays.fill(f, 1); // worst case, which is monotonic decreasing sequence int len = 0; for(int i=1; i<num.length; i++) { for(int j=0; j<i; j++) { if(num[j] <= num[i]) { f[i] = Math.max(f[i], f[j]+1); } } len = Math.max(len, f[i]); } return len; }
该算法的时间复杂度是O(n2 ),并不是最优的解法。 还有一种很巧妙的算法可以将时间复杂度降到O(nlogn),网上已经有各种文章介绍它, 这里就不再赘述。传送门: LIS的O(nlogn)解法。 此题还可以用“排序+LCS”来解,感兴趣的话可自行Google。
//在非递减序列 arr[s..e](闭区间)上二分查找第一个大于等于key的位置,如果都小于key,就返回e+1 int upper_bound(int arr[], int s, int e, int key) { int mid; if (arr[e] <= key) return e + 1; while (s < e) { mid = s + (e - s) / 2; if (arr[mid] <= key) s = mid + 1; else e = mid; } return s; } int LIS(int d[], int n) { int i = 0, len = 1, *end = (int *)calloc(sizeof(int) * (n + 1)); end[1] = d[0]; //初始化:长度为1的LIS末尾为d[0] for (i = 1; i < n; i++) { int pos = upper_bound(end, 1, len, d[i]); //找到插入位置 end[pos] = d[i]; if (len < pos) //按需要更新LIS长度 len = pos; } return len; }
下面是上述思路的Java解法。
这次dp[i]用来记录长度为i的最长子序列的最后一个数最小是多少,可以知道dp[i] < dp[j] (i < j)。
在二分查找时,一直更新dp数组,设此时dp的总长度为k,
若1. A[i] >= dp[k], 则dp[k+1] = A[i];
若2. A[i] < dp[k], 则在dp[1..k]中用二分搜索大于A[i]的最小值,返回其位置pos,然后更新dp[pos] = A[i]。
public int longestIncreasingSubsequence1(int[] num) { int[] f = new int[num.length+1]; f[1] = num[0]; int len = 1; for(int i=1; i<num.length; i++) { if(num[i] >= f[len]) { f[++len] = num[i]; } else { int pos = binarySearch(f, 1, len, num[i]); f[pos] = num[i]; } } return len; } private int binarySearch(int[] f, int start, int end, int target) { while(start<end) { int mid = (start+end)/2; if(f[mid] <= target) { start = mid + 1; } else { end = mid; } } return start; }
Reference:
http://www.hawstein.com/posts/dp-novice-to-advanced.html
https://shepherdyuan.wordpress.com/2014/07/29/lis-longest-increasing-subsequence/
相关推荐
LMS Longest Monotonically Increasing Sequence Algorithm
Estimating the Longest Increasing Subsequence in Nearly Optimal Time_在近似最优时间内估计最长增长子序列.pdf
java动态规划的最长公共子序列算法和最长递增子序列算法
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
关于Longest Common Subsequences演算法
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
Longest Ordered Subsequence,算法分析与设计,C语言程序
Longest Common Ancestor classic ppt...
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
LeetCode Longest Common Prefix解决方案
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
2.2.2 最长递增子序列(Longest increasing subsequence) 2.2.3 Sequence alignment 2.2.4 最长相同子序列(Longest common subsequence) 2.3.5 Matrix-chain multiplication 2.3.6 树上的独立集 (Max ...
Brian Dean 在MIT教算法课录制的10个动态规划问题的视频动画。 包含 ...- longest increasing subsequences - making changes - maximum value contiguous subsequences - optimal strategy for a game
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
Increasing Subsequence | LongestPalindromicSubstring.java 5. Longest Palindromic Substring │ RansomNote.java //383. Ransom Note │ RussianDollEnvelope.java //354. Russian Doll Envelopes │ ...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的...