最长递增子序列 动态规划_最长公共子序列动态规划

 1 import java.util.Arrays;
 2 
 3 public class LongestIncreasingSubsequence {
 4     public static void main(String[] args) {
 5         int[] numbers = {5, 2, 8, 6, 3, 6, 9, 5};
 6         System.out.println(Arrays.toString(numbers));
 7         recursive(numbers);
 8     }
 9 
10     public static void recursive(int[] numbers) {
11         //从左到右依次计算截止到每个数字的最长递增子序列的长度
12         for (int i = 0; i < numbers.length; i++) {
13             System.out.printf("index=%d num=%d max=%d\n", i, numbers[i], cmp(numbers, i));
14         }
15     }
16 
17     private static int cmp(int[] numbers, int k) {
18         //数据中第一个位置的最长子序列是1
19         if (k == 0) {
20             return 1;
21         }
22         //小于当前数字（基准数字）的列表中最大的子序列长度，默认长度为1
23         int max = 1;
24         //从左侧第一个位置开始依次和基准数字对比
25         for (int i = 0; i < k; i++) {
26             //小于基准数字，说明可以组成递增子序列
27             if (numbers[i] < numbers[k]) {
28                 //取截至到k对应数字的最大子序列长度。反应到当前基准数字的列长度需要返回结果+1
29                 int length = cmp(numbers, i) + 1;
30                 //取所有小于基准数字中最大的那一个数
31                 if (length > max) {
32                     max = length;
33                 }
34             }
35         }
36         return max;
37     }
38 }

[5, 2, 8, 6, 3, 6, 9, 5]
index=0 num=5 max=1
index=1 num=2 max=1
index=2 num=8 max=2
index=3 num=6 max=2
index=4 num=3 max=2
index=5 num=6 max=3
index=6 num=9 max=4
index=7 num=5 max=3

 1     public static void dp(int[] numbers) {
 2         //保存每个数字的下标对应的最长递增子序列长度值
 3         int[] dp = new int[numbers.length];
 4         //数据初始化：每个数字对应的默认序列长度都是1
 5         for (int i = 0; i < dp.length; i++) {
 6             dp[i] = 1;
 7         }
 8         System.out.println(Arrays.toString(dp));
 9 
10         //由于第一个位置（index=0）不存在前驱数字，也就无需比较，直接从index=1开始即可。
11         for (int i = 1; i < numbers.length; i++) {
12             System.out.printf("index=%d num=%d\n", i, numbers[i]);
13             //当前数字和之前的依次比较
14             for (int j = 0; j < i; j++) {
15                 //小于当前数字说明是一个递增序列，序列长度可以加1
16                 if (numbers[i] > numbers[j]) {
17                     System.out.printf("\t%d>%d dp[%d]=%d dp[%d]=%d\n", numbers[i], numbers[j], i, dp[i], j, dp[j]);
18                     //但需要取最大的
19                     if (dp[j] + 1 > dp[i]) {
20                         dp[i] = dp[j] + 1;
21                     }
22                 } else {
23                     System.out.printf("\t%d<=%d skip\n", numbers[i], numbers[j]);
24                 }
25             }
26             System.out.printf("\tdp[%d]=%d %s\n", i, dp[i], Arrays.toString(dp));
27         }
28     }

[dp]
[1, 1, 1, 1, 1, 1, 1, 1]
index=1 num=2
	2<=5 skip
	dp[1]=1 [1, 1, 1, 1, 1, 1, 1, 1]
index=2 num=8
	8>5 dp[2]=1 dp[0]=1
	8>2 dp[2]=2 dp[1]=1
	dp[2]=2 [1, 1, 2, 1, 1, 1, 1, 1]
index=3 num=6
	6>5 dp[3]=1 dp[0]=1
	6>2 dp[3]=2 dp[1]=1
	6<=8 skip
	dp[3]=2 [1, 1, 2, 2, 1, 1, 1, 1]
index=4 num=3
	3<=5 skip
	3>2 dp[4]=1 dp[1]=1
	3<=8 skip
	3<=6 skip
	dp[4]=2 [1, 1, 2, 2, 2, 1, 1, 1]
index=5 num=6
	6>5 dp[5]=1 dp[0]=1
	6>2 dp[5]=2 dp[1]=1
	6<=8 skip
	6<=6 skip
	6>3 dp[5]=2 dp[4]=2
	dp[5]=3 [1, 1, 2, 2, 2, 3, 1, 1]
index=6 num=9
	9>5 dp[6]=1 dp[0]=1
	9>2 dp[6]=2 dp[1]=1
	9>8 dp[6]=2 dp[2]=2
	9>6 dp[6]=3 dp[3]=2
	9>3 dp[6]=3 dp[4]=2
	9>6 dp[6]=3 dp[5]=3
	dp[6]=4 [1, 1, 2, 2, 2, 3, 4, 1]
index=7 num=5
	5<=5 skip
	5>2 dp[7]=1 dp[1]=1
	5<=8 skip
	5<=6 skip
	5>3 dp[7]=2 dp[4]=2
	5<=6 skip
	5<=9 skip
	dp[7]=3 [1, 1, 2, 2, 2, 3, 4, 3]