动态规划 Dynamic Programming

使用l(i)表示前i个元素中上升子序列长度的最大值,

1
2
3
4
5
6
7
8
对于序列{5, 2, 7, 4, 8, 12, 9, 10, 14},
l(0) = 1;
a[1] <= a[0], l(1) = 1;
a[2] > a[1], l(2) = l(1) + 1 = 2;
a[3] <= a[2], l(3) = l(2) = 2;
a[4] > a[3], l(4) = l(3) + 1 = 3;
...

可以得到状态转移方程:

1
2
i = 0时, l(i) = 1
i > 0时, l(i) = a[i] > a[i - 1] ? l(i - 1) + 1 : l(i - 1)

具体的程序实现:

1
2
3
4
5
6
7
8
9
10
int LIS(int[] a) {
int[] l = new int[a.length];
l[0] = 1;
for(int i = 1; i < a.length; i++) {
l[i] = a[i] > a[i - 1] ? l[i - 1] + 1 : l[i - 1];
}
return l[a.length];
}
得到最长上升子序列

与前面思路相同,换一种方式实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Object[] LIS(int[] array) {
// 使用线性表保存LIS
java.util.ArrayList<Integer> list = new java.util.ArrayList<Integer>();
list.add(array[0]);
for(int i = 1; i < array.length; i++) {
// 等价于a[i] > a[i - 1],l[i] = l[i - 1] + 1
if(array[i] > list.get(list.size() - 1))
list.add(array[i]);
// 使LIS末尾的元素在满足LIS条件的前提下尽可能小
// 等价于a[i] <= a[i - 1],l[i] = l[i]
else if(list.size() - 2 < 0 || array[i] > list.get(list.size() - 2)) {
list.remove(list.size() - 1);
list.add(array[i]);
}
}
return list.toArray();
}
参考资料

通过金矿模型介绍动态规划