本文主要是介绍动态规划---序列问题（最长公共，最长递增，最长公共递增，最长数对，最长摆动），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.最长递增子序列
/** 最长递增子序列* */public int lengthOfLIS(int[] nums) {//方案一：时间复杂度0(N^2)int n = nums.length;if (n == 0) return 0;int dp[] = new int[n];//dp[i]表示以i元素结尾最长递增子序列的长度dp[0] = 1;int maxL = 1;for (int i = 1; i < n; i++) {dp[i] = 1;//注意这个位置for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxL = Math.max(maxL, dp[i]);}return maxL;}/** 维持一个有序数组tail[],tail[i]表示递增子序列长度为i+1时，最末尾的最小元素.* */public int lengthOfLIS2(int[] nums) {//方案二：时间复杂度0(NlogN)int n = nums.length;if (n == 0) return 0;int tail[]=new int[nums.length];tail[0]=nums[0];int j=0;/** 遍历所有元素。* 如果它大于 tails 数组所有的值，那么把它添加到 tails 后面，表示最长递增子序列长度加 1* 如果 tails[i-1] < x <= tails[i]，那么更新 tails[i] = x。* */for(int i=1;i<nums.length;i++){int index=binarySearch(tail,j,nums[i]);tail[index]=nums[i];if(index==j+1) j++;}return j+1;}public int binarySearch(int a[],int count,int k){//找到第一个大于或等于k的元素索引(找到大于等于k的最小元素的索引),如果找不到返回count+1int start=0;int end=count;int index=-1;int elem=Integer.MAX_VALUE;while (start<=end){int mid=(start+end)/2;if(k<=a[mid]){if(a[mid]<elem) {elem = a[mid];index = mid;}end=mid-1;}else{start=mid+1;}}return index==-1?count+1:index;}
2. 一组整数对能够构成的最长链
/** 最长数对链* 题目描述：* 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。* 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。* 给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。* *///动态规划方法解决public int findLongestChain(int[][] pairs) {int num = 0;int n = pairs.length;if (n == 0) return 0;Arrays.sort(pairs, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] - o2[0];}});int dp[] = new int[n];//dp[i]表示以第i个数对结尾的最大长度int max = 1;for (int i = 0; i < pairs.length; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (pairs[i][0] > pairs[j][1]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}max = Math.max(max, dp[i]);}return max;}//贪心方法解决public int findLongestChain2(int[][] pairs) {/** 优先选择数对 尾值更小的，给 组合后面的数对 留更多的机会* */if (pairs == null || pairs.length == 0) return 0;int n = pairs.length;Arrays.sort(pairs, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[1] - o2[1];}});int curEnd = pairs[0][1];int sum = 1;for (int i = 1; i < n; i++) {if (pairs[i][0] > curEnd) {sum++;curEnd = pairs[i][1];}}return sum;}
3.最长摆动子序列
/** 摆动序列* 题目描述：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。* 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。* 思路：见程序中注释* 解释：up,down的每一次更新（up=down+1，down=up+1），都意味着更新了 最长摆动子序列的末尾curEnd，虽然最长长度可能没更新。* 连续上升（下降），最长长度不会变，变的是最长摆动子序列的末尾curEnd* （隐晦一点解释：有升才有降，有降才有升）* */public int wiggleMaxLength(int[] nums) {int down = 1;//down维护了此时 摆动序列以down操作结尾的 最长长度int up = 1; //up维护了此时 摆动序列以up操作结尾的 最长长度for (int i = 1; i < nums.length; i++) {if (nums[i] > nums[i - 1]) {up = down + 1;//up在down的基础上上升} else if (nums[i] < nums[i - 1]) {down = up + 1;//down在up的基础上下降}}/** 解决质疑：* 1.连续下降时,程序为什么将curEnd更新为后面的，也就是说为什么curEnd会更新为越小的值？* 因为在等待下一次上升时，只要比curEnd大，就可以完成上升操作。所以curEnd越小，上升的机会就越大，那么累计的序列就越长* 2.会不会出现 在等待下降时，隔了很多个元素才满足下降条件，就累计不到了 这种情况？* 不会。例如序列[4,5,7,8,9,3] 在4等待下降时，直观来看，4和3之间隔了很多个元素,这几个元素一定都会比4大， 程序早已将curEnd更新为了9,9>3则累计。* 再例如序列[4,9,6,8,7,3] 在4等待下降时，直观来看，4和3之间隔了很多元素， 这些元素呈现了一个摆动状态，能确保者之间的摆动被累计了吗？* 可以确保，其实，当元素遍历到9时curEnd不再是4，而是9了（虽然最长长度没更新，但最长摆动子序列的末尾curEnd被更新了），然后再继续累计9下降到6的情况，以此类推。* */return Math.min(nums.length, Math.max(down, up));}
4.最长公共子序列
/** dp[i][j]表示S1前i个字符和S2前j个字符的最长公共子序列的长度值* 当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即 dp[i][j] = dp[i-1][j-1] + 1。* 当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。* */public int longestCommonSubsequence2(String S1, String S2) {int len1 = S1.length();int len2 = S2.length();if (len1 == 0 || len2 == 0) return 0;int dp[][]=new int[len1+1][len2+1];int book[][]=new int[len1+1][len2+1];//记录dp[i][j]的更新情况，找到最长公共子序列for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){if(S1.charAt(i-1)==S2.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;book[i][j]=1;//代表最大值在此时更新}else{if(dp[i-1][j]>dp[i][j-1]){dp[i][j]=dp[i-1][j];book[i][j]=2;//代表更新为dp[i-1][j]的值}else{dp[i][j]=dp[i][j-1];book[i][j]=3;//代表更新为dp[i][j-1]的值}}}}int i=len1,j=len2;while (i>=0&&j>=0){if(book[i][j]==1) {System.out.print(S1.charAt(i-1)+" ");i--;j--;}else if(book[i][j]==2) i--;else j--;}return dp[len1][len2];//最长公共子序列的长度}
5.最长公共递增子序列
public class MaxLenOfCommonIncrease {//只过了80%，超时了public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();while (n-- != 0) {int l1 = scanner.nextInt();int s1[] = new int[l1];for (int i = 0; i < l1; i++) {s1[i] = scanner.nextInt();}int l2 = scanner.nextInt();int s2[] = new int[l2];for (int j = 0; j < l2; j++) {s2[j] = scanner.nextInt();}int dp[][] = new int[l1][l2];//dp[i][j]表示s1列表中前i个元素，s2列表中前j个元素，并且以s2[j]为末尾的最长公共递增序列的长度for(int j=0;j<l2;j++) dp[0][j]= s1[0]==s2[j]?1:0;for(int i=0;i<l1;i++) dp[i][0]= s2[0]==s1[i]?1:0;for(int i=1;i<l1;i++){for(int j=1;j<l2;j++){dp[i][j]=dp[i-1][j];if(s1[i]==s2[j]){for(int k=0;k<j;k++){if(s2[j]>s2[k]) dp[i][j]=Math.max(dp[i][j],dp[i-1][k]+1);}dp[i][j]=Math.max(1,dp[i][j]);}}}int res = 0;for (int j = 0; j < l2; ++j)res = Math.max(res, dp[l1-1][j]);System.out.println(res);}}
}
/*
这种方法可以全过，但不是很懂public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();while (n-- != 0) {int l1 = scanner.nextInt();int s1[] = new int[l1];for (int i = 0; i < l1; i++) {s1[i] = scanner.nextInt();}int l2 = scanner.nextInt();int s2[] = new int[l2];for (int j = 0; j < l2; j++) {s2[j] = scanner.nextInt();}int dp[][] = new int[505][505];for (int i = 0; i <l1; i++) {int max = 0;for (int j = 0; j <l2; j++) {dp[i + 1][j + 1] = dp[i][j + 1];if (s1[i] > s2[j])max = Math.max(max, dp[i][j + 1]);if (s1[i] == s2[j]) {dp[i + 1][j + 1] = max + 1;}}}int res = 0;for (int j = 1; j <= l2; ++j)res = Math.max(res, dp[l1][j]);System.out.println(res);}}*/
这篇关于动态规划---序列问题（最长公共，最长递增，最长公共递增，最长数对，最长摆动）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
