/**
-
@author yinxin
-
@version 1.0
-
@Description: 叠书：给定一个二维数组类似于"[[20,16],[20,21],[10,20],[9,10]]"，
-
对于二维数组的每一个元素：第一个元素表示书的宽度，第二个元素表示书的高度，
-
叠在上面的书比在下面的书宽度和高度都要小，求最多能叠的书的数量
-
@date 2022/5/915:37
*/
public class Exercise8 {
public static void main(String[] args) {
int[][] arr = {{20,16},{20,21},{10,20},{9,10},{64,45},{42,95},{80,37},{79,84},
{51,23},{13,15},{60,69},{32,88},{53,91},{91,87},{57,30},{83,84}};//定义数组
//先排第一个数
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j][0]>arr[j+1][0]){
swapArr(arr,j,j+1);
}
}
}
int[] myArr = new int[arr.length];
//排序(第一个数字排序，小到大)
for (int i = 0; i < arr.length; i++) {
myArr[i]=arr[i][1];
}
//System.out.println(Arrays.toString(myArr));
long times = System.currentTimeMillis();
LIS lis = new LIS(myArr);
int foo1 = lis.foo();
System.out.println(“动态规划使用的时间是：”+(System.currentTimeMillis()-times));
System.out.println(“结果是:”+foo1);
times=System.currentTimeMillis();
int foo2 = foo(myArr, myArr.length - 1);
System.out.println(“不用动态规划使用的时间是：”+(System.currentTimeMillis()-times));
System.out.println(“结果是:”+foo2);
}/public static void main(String[] args){
int[] arr = new int[31];
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
}/
// 最长递增子序列
private static class LIS {
// longest increasing subsequence
int[] arr;
HashMap<Integer,Integer> values = new HashMap<>();
LIS(int[] arr) {
this.arr = arr;
}
int foo() {
return foo(arr, arr.length - 1);
}
private int foo(int[] arr, int end) {
//先从动态规划存储的foo(arr,end)的结果中拿到存储的值，拿不到就要走逻辑计算。
Integer value = values.get(end);
if (value != null) {
return value;
}
if (end == 0) {
values.put(0, 1);//每次返回时存值
return 1;
}
int len = 0;
for (int i = 0; i < end; i++) {
int temp = foo(arr, i);
len = Math.max(len, arr[end] > arr[i] ? temp + 1 : temp);
}
values.put(end, len);//每次返回时存值
return len;
}
}private static int foo(int[] arr, int end) {
if (end == 0) {
return 1;
}
/** 设计思路–
* 设 foo(k) 对应代码中的foo(int[] arr, int end)为：
* 以数列中第k项 (为了与java数组逻辑一致，这里的k从0开始计算) 结尾的最长递增子序列的长度
* 则：
* foo(0) == 1
* foo(k) == max(
* arr[k]>arr[0]?foo(0)+1:foo(0),
* arr[k]>arr[1]?foo(1)+1:foo(1) ,
* … ,
* arr[k]>arr[k-1]?foo(k-1)+1:foo(k-1)
* )
*/
int len = 0;
for (int i = 0; i < end; i++) {
int temp = foo(arr,i);
len = Math.max(len,arr[end]>arr[i]?temp+1:temp);//这里的len是foo(i-1)的值
}
return len;
}public static void swapArr(int[][] arr, int after, int before) {
int[] tmp = arr[after];
arr[after] = arr[before];
arr[before] = tmp;
}
}
