文章目录
- 前言
- 一、问题描述
- 二、DP步骤
-
- 1、最优子结构
-
- a、限界上升子序列
- b、最优子结构性质
- a、限界上升子序列
- 2、状态表示和递推方程
- 3、计算最优值
- 4、算法实现
- 三、优化：非DP /二分法
-
- 1、新问题
- 2、算法实现
前言
一、问题描述
二、DP步骤
1、最优子结构
- 给定序列𝑆=[𝑠1,𝑠2,⋯,𝑠𝑛]，如果子序列[𝑆(𝑖1 ),𝑆(𝑖2 ), ⋯,𝑆(𝑖𝑘 )]是其最大上升子序列，则[𝑆(𝑖1 ),𝑆(𝑖2 ), ⋯,𝑆(𝑖(𝑘−1) )]是子问题𝑆=[𝑠1,𝑠2,⋯,𝑆(𝑖(𝑘−1) )]的最大上升子序列吗？
- 例：给定 S = [1, 3, 4, 2, 7, 9, 6, 8]，最大上升子序列可为 [1, 3, 4, 6, 8]，最大长度为5。
- [1, 3, 4, 6]显然不是[1, 3, 4, 2, 7, 9, 6]的最大上升子序列，因为[1, 3, 4, 7, 9]是其最大上升子序列。
注意：可以同时有多个最大上升子序列！每个的最大值都不相同 - 如果直接把最大上升子序列的长度作为规划目标，那么该问题不具备最优子结构性质（因为可能同时有多个最大上升子序列，使得最优子结构不成立）。只能采用间接的办法，引入一些中间目标作为动态规划的对象。
a、限界上升子序列
b、最优子结构性质
2、状态表示和递推方程
公式讲解：只求长度，不求具体的子序列
- 逐一找出1—（m-1）个元素中所有小于Sm的元素Si及其对应的Len(Si)值，然后从中取最大的一个Len(.)值，然后加1。【 1–i个元素中所有大于Sm的元素的Len(.)值全都不予考虑】
- 如果精简为max{Len(i)+1 | 1≤i
<m, Sm>Si}，可以吗？
sure
3、计算最优值
- 𝐿𝑒𝑛(𝑚)的计算同样按照自底向上的顺序进行：所有子问题的总数为n个(即，分别以每个元素为限界)；m越小，其子问题𝐿𝑒𝑛(𝑚)求解的复杂度就越低
- 当所有的𝐿𝑒𝑛(𝑚)(1≤𝑚≤𝑛)都计算完毕后，统计其中最大值，即可得到输入序列 S 的最大上升子序列
- 注意：最大上升子序列的长度不一定等于𝑳𝒆𝒏(𝒏)
答案详解：
1、 Len(1)=1；
2、 Len(3)=2：找到3之前小于3的数字中，最大的Len(.)值加1，即：len(1)+1=1；
3、 Len(4)=3：找到4之前小于4的数字：1和3，最大Len(.)值加1，即：len(3)+1=3；
4、 Len(2)=2：找到2之前小于2的数字：1，最大Len(.)值加1，即：Len(1)+1=2；
5、 Len(7)=4：找到7之前小于7的数字：1，3，4，2，最大Len(.)值加1，即：Len(4)+1=4；
6、 Len(6)=4：找到6之前小于6的数字：1，3，4，2，最大Len(.)值加1，即：Len(4)+1=4；
7、 Len(8)=5：找到8之前小于8的数字：1，2，3，2，7，6，最大Len(.)值加1，即：Len(7)+1=5或者Len(6)+1=5；
4、算法实现
时间复杂度：n2
/**
* DP算法之最大上升子序列问题
*/
public class Main4 {
public static int MAXN = 100;
public static void main(String[] args) {
int[] seqSrc = {
1, 3, 4, 2, 7, 6, 8};
int i = LISLength(7, seqSrc);
System.out.println(i);
}
public static int LISLength(int num, int[] seqSrc) {
int[] Len = new int[MAXN];
int res = 1;
//设第m个数的值为上界
for (int m = 0; m < num; m++) {
//每个新m为上界时，Len[m]总是从1开始
Len[m] = 1;
for (int i = 0; i < m; i++)
//遍历所有以第i个数为上界的长度，从中选出符合max公式条件的最大值加1，就是Len[m]。
if (seqSrc[i] < seqSrc[m] && Len[i] + 1 > Len[m])
Len[m] = Len[i] + 1;
//记录从len[1]到len[m]中的最大值，res为最大公共子序列长度，最后的解
res = (res > Len[m] ? res : Len[m]);
}
return res;
}
}
代码解说：
1、 第一个for遍历：有几个元素就遍历几个，计算每个的Len(.)值；
2、 第二个for遍历：遍历当前元素的最大Len(.)值；
seqSrc[i] < seqSrc[m]：过滤小于当前元素的值，Len[i] + 1 > Len[m]：找到最大值
三、优化：非DP /二分法
时间复杂度 nlog2n。
1、新问题
上图中的公式中的 i ，为数组的下标
例：
1、 k=4的值有两个，Len(5)=4，Len(6)=4；
2、 S[5]=7,S[6]=6；
3、 所以T[k=4]=6；
2、算法实现
/**
* DP之最大上升子序列：时间复杂度 nlog2n
*/
public class Main5 {
public static void main(String[] args) {
int[] seqSrc = {
1, 3, 4, 2, 7, 6, 8};
int i = lengthOfLIS(seqSrc);
System.out.println(i);
}
public static int lengthOfLIS(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[] ends = new int[arr.length];
ends[0] = arr[0];
int right = 0;
int l = 0;
int r = 0;
int m = 0;
int max = 1;
for (int i = 1; i < arr.length; i++) {
l = 0;
r = right;
while (l <= r) {
m = (l + r) / 2;
if (arr[i] > ends[m]) {
l = m + 1;
} else {
r = m - 1;
}
}
right = Math.max(right, l);
ends[l] = arr[i];
max = Math.max(max, l + 1);
}
return max;
}
}
