ShiYu

# 第20节 暴力递归到动态规划（三）

暴力递归改动态规划步骤：

  • 一定要尝试出暴力递归版本，设计暴力递归：重要原则+4种常见尝试模型
    • 从左往右的尝试模型
    • 范围上的尝试模型
    • 多样本位置全对应的尝试模型
    • 寻找业务限制的尝试模型
  • 分析有无重复解
  • 用记忆化搜索实现
    • 分析可变参数范围
    • 写出basecase程式
    • 分析普遍位置依赖
    • 最终推出严格表结构实现动态规划
  • 继续看严格表结构是否可再优化
    • 若是普遍位置求解部分已经是O(1)，不用再优化了
    • 若是普遍位置求解部分是需要遍历的，则尝试使用斜率优化、临近位置观察法优化

设计暴力递归过程的原则：

1）每一个可变参数的类型，一定不要比int类型更加复杂

2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数 例如：贴纸问题

3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可

4）可变参数的个数，能少则少

# 题目一

最长回文子序列

给定一个字符串str，返回这个字符串的最长回文子序列长度 比如 ： str = “a12b3c43def2ghi1kpm” 最长回文子序列是“1234321”或者“123c321”，返回长度7

暴力递归代码：

  • 将str逆序得到rstr，求这两个字符串的最长公共子序列长度就是str字符串的最长回文子序列长度
  • 使用范围模型，推出暴力递归代码
package class20;

/**
 * - 最长回文子序列
 * - 给定一个字符串str，返回这个字符串的最长回文子序列长度
 * - 比如 ： str = “a12b3c43def2ghi1kpm”
 * - 最长回文子序列是“1234321”或者“123c321”，返回长度7
 * @author yangyanchao
 *
 */
//测试链接：https://leetcode.com/problems/longest-palindromic-subsequence/
public class Test01_PalindromeSubsequence {
	
	/**
	 * - 最长回文子序列-暴力递归版本
	 * @param s
	 * @return
	 */
	public static int longestPalindromeSubseq1(String s) {
		if(s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		return process1(str, 0, N - 1);
	}

	/**
	 * 	递归过程- 返回str在L...R范围上的最长回文子序列
	 * @param str
	 * @param L
	 * @param R
	 * @return
	 */
	private static int process1(char[] str, int L, int R) {
		if(L == R) {
			// 只有一个字符时 最长回文子序列就是1
			return 1;
		}
		if(L == R - 1) {
			// 有两个字符时 
			// 若str[L] == str[R]最长回文子序列就是2
			// 若str[L] != str[R]最长回文子序列就是1
			return str[L] == str[R] ? 2 : 1;
		}
		// 要么最长回文子序列不以str[L]开头、不以str[R]结尾
		int p1 = process1(str, L + 1, R - 1);
		// 要么最长回文子序列以str[L]开头、不以str[R]结尾
		int p2 = process1(str, L, R - 1);
		// 要么最长回文子序列不以str[L]开头、以str[R]结尾
		int p3 = process1(str, L + 1, R);
		// 要么最长回文子序列以str[L]开头、以str[R]结尾 并且str[L]==str[R]
		int p4 = str[L] == str[R] ? (2 + process1(str, L + 1, R - 1)) : 0;
		return Math.max(Math.max(p1, p2), Math.max(p3, p4));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

分析位置依赖：

假设：

char[] str=['1','2','b','3','4','4','3','2','a','1']

需要10*10的表格dp[L][R]=dp[10][10]，由于L<R所以表格的左下半部分是无效的

分析basecase：

L==R -> 1 L==R-1 -> str[L] == str[R] ? 2 : 1

分析递归题的位置依赖：

普通位置比如&位置dp[6][9]

它依赖的位置是dp[L+1][R-1](左下位置) dp[L][R-1](左位置) dp[L+1][R](下位置)

所以得出遍历的顺序为从底向上，从左往右遍历

0 1 2 3 4 5 6 7 8 9
0 1 1 @29 @30 @31 @32 @33 @34 @35 @36
1 -1 1 1 @22 @23 @24 @25 @26 @27 @28
2 -1 -1 1 1 @16 @17 @18 @19 @20 @21
3 -1 -1 -1 1 1 @11 @12 @13 @14 @15
4 -1 -1 -1 -1 1 2 @7 @8 @9 @10
5 -1 -1 -1 -1 -1 1 1 @4 @5 @6
6 -1 -1 -1 -1 -1 -1 1 1 @2 &@3
7 -1 -1 -1 -1 -1 -1 -1 1 1 @1
8 -1 -1 -1 -1 -1 -1 -1 -1 1 1
9 -1 -1 -1 -1 -1 -1 -1 -1 -1 1

最终求dp[0][9]

动态规划代码：

package class20;

/**
 * - 最长回文子序列
 * - 给定一个字符串str，返回这个字符串的最长回文子序列长度
 * - 比如 ： str = “a12b3c43def2ghi1kpm”
 * - 最长回文子序列是“1234321”或者“123c321”，返回长度7
 * @author yangyanchao
 *
 */
//测试链接：https://leetcode.com/problems/longest-palindromic-subsequence/
public class Test01_PalindromeSubsequence {
	
	/**
	 * - 最长回文子序列-动态规划版本
	 * @param s
	 * @return
	 */
	public static int longestPalindromeSubseq(String s) {
		if(s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		int [][] dp = new int[N][N];
		// 设置两basecase位置
		// 小技巧 先设置dp[N-1][N-1] 这样为了下面的代码不越界处理
		dp[N - 1][N - 1] = 1;
		int i = 0;
		for(; i < N - 1; i++) {
			dp[i][i] = 1;
			dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
		}
		int R = 0;
		int L = 0;
		// 设置普通位置
		for(L = N - 3; L >= 0; L--) {
			for(R = L + 2; R < N; R++) {
				int p1 = dp[L + 1][R - 1];
				int p2 = dp[L][R - 1];
				int p3 = dp[L + 1][R];
				int p4 = str[L] == str[R] ? (2 + dp[L + 1][R - 1]) : 0;
				dp[L][R] = Math.max(Math.max(p1, p2), Math.max(p3, p4));
			}
		}
		return dp[0][N - 1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

分析位置X依赖得出：X依赖的位置是dp[L+1][R-1](左下位置) dp[L][R-1](左位置) dp[L+1][R](下位置)，但是X位置上的数一定比这三个位置的数大，因为是求得最大值的，所以左位置一定比左下位置大和下位置一定比左下位置大，结论就是可以不考虑左下位置了

动态规划再次优化版本代码：

package class20;

/**
 * - 最长回文子序列
 * - 给定一个字符串str，返回这个字符串的最长回文子序列长度
 * - 比如 ： str = “a12b3c43def2ghi1kpm”
 * - 最长回文子序列是“1234321”或者“123c321”，返回长度7
 * @author yangyanchao
 *
 */
//测试链接：https://leetcode.com/problems/longest-palindromic-subsequence/
public class Test01_PalindromeSubsequence {
	/**
	 * - 最长回文子序列-动态规划再次优化版本
	 * @param s
	 * @return
	 */
	public static int longestPalindromeSubseq(String s) {
		if(s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		int [][] dp = new int[N][N];
		// 设置两basecase位置
		// 小技巧 先设置dp[N-1][N-1] 这样为了下面的代码不越界处理
		dp[N - 1][N - 1] = 1;
		int i = 0;
		for(; i < N - 1; i++) {
			dp[i][i] = 1;
			dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
		}
		int R = 0;
		int L = 0;
		// 设置普通位置
		for(L = N - 3; L >= 0; L--) {
			for(R = L + 2; R < N; R++) {
				dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
				if(str[L] == str[R]) {
					dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
				}
			}
		}
		return dp[0][N - 1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# 题目二

象棋走马问题

请同学们自行搜索或者想象一个象棋的棋盘， 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域 给你三个 参数 x，y，k 返回“马”从(0,0)位置出发，必须走k步 最后落在(x,y)上的方法数有多少种?

暴力递归代码：

package class20;

/**
 * - 象棋走马问题
 * - 请同学们自行搜索或者想象一个象棋的棋盘，
 * - 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
 * - 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
 * - 给你三个 参数 x，y，k
 * - 返回“马”从(0,0)位置出发，必须走k步
 * - 最后落在(x,y)上的方法数有多少种?
 * @author yangyanchao
 *
 */
public class Test02_HorseJump {
	
	
	/**
	 * - 象棋走马问题-暴力递归版本
	 * @param a
	 * @param b
	 * @param k
	 * @return
	 */
	public static int jump1(int a, int b, int k) {
		if(a > 8 || b > 9 || k < 1) {
			return -1;
		}
		return process(0, 0, a, b, k);
	}

	/**
	 * 	马从(x, y)点开始走rest步到(a,b)点的有多少种方法
	 * @param x
	 * @param y
	 * @param a
	 * @param b
	 * @param rest
	 * @return
	 */
	private static int process(int x, int y, int a, int b, int rest) {
		if(x < 0 || y < 0 || x > 8 || y > 9) {
			// 马走偏了 0种可能
			return 0;
		}
		if(rest == 0) {
			// 剩余步数是0步
			// 若是正好走到了(a,b)点则返回1
			// 若不是则返回0
			return (x == a && y == b) ? 1 : 0;
		}
		// 1)马走左上立日(x+1,y+2)
		int ways = process(x + 1, y + 2, a, b, rest - 1);
		// 2)马走右上立日(x-1,y+2)
		ways += process(x - 1, y + 2, a, b, rest - 1);
		// 3)马走左上倒日(x+2,y+1)
		ways += process(x + 2, y + 1, a, b, rest - 1);
		// 4)马走右上倒日(x-2,y+1)
		ways += process(x - 2, y + 1, a, b, rest - 1);
		// 5)马走左下立日(x+1,y-2)
		ways += process(x + 1, y - 2, a, b, rest - 1);
		// 6)马走右下立日(x-1,y-2)
		ways += process(x - 1, y - 2, a, b, rest - 1);
		// 7)马走左下倒日(x+2,y-1)
		ways += process(x + 2, y - 1, a, b, rest - 1);
		// 8)马走右下倒日(x-2,y-1)
		ways += process(x - 2, y - 1, a, b, rest - 1);
		return ways;
	}
	
	public static void main(String[] args) {
		int x = 7;
		int y = 7;
		int step = 10;
		// 515813
		System.out.println(jump1(x, y, step));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

动态规划代码：

package class20;

/**
 * - 象棋走马问题
 * - 请同学们自行搜索或者想象一个象棋的棋盘，
 * - 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
 * - 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
 * - 给你三个 参数 x，y，k
 * - 返回“马”从(0,0)位置出发，必须走k步
 * - 最后落在(x,y)上的方法数有多少种?
 * @author yangyanchao
 *
 */
public class Test02_HorseJump {
	
	/**
	 * - 象棋走马问题-动态规划版本
	 * @param a
	 * @param b
	 * @param k
	 * @return
	 */
	public static int jump2(int a, int b, int k) {
		if(a > 8 || b > 9 || k < 1) {
			return -1;
		}
		int[][][] dp = new int[9][10][k + 1];
		dp[a][b][0] = 1;
		for(int step = 1; step <= k; step++) {
			for(int x = 0; x < 9; x++) {
				for(int y = 0; y < 10; y++) {
					int ways = pick(dp, x + 2, y + 1, step - 1);
					ways += pick(dp, x + 1, y + 2, step - 1);
					ways += pick(dp, x - 1, y + 2, step - 1);
					ways += pick(dp, x - 2, y + 1, step - 1);
					ways += pick(dp, x - 2, y - 1, step - 1);
					ways += pick(dp, x - 1, y - 2, step - 1);
					ways += pick(dp, x + 1, y - 2, step - 1);
					ways += pick(dp, x + 2, y - 1, step - 1);
					dp[x][y][step] = ways;
				}
			}
		}
		return dp[0][0][k];
	}
	
	private static int pick(int[][][] dp, int x, int y, int k) {
		if(x < 0 || y < 0 || x > 8 || y > 9) {
			return 0;
		}
		return dp[x][y][k];
	}

	public static void main(String[] args) {
		int x = 7;
		int y = 7;
		int step = 10;
		// 515813
		System.out.println(jump2(x, y, step));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

# 题目三

泡咖啡问题

给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间 给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡 只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯 每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发 假设所有人拿到咖啡之后立刻喝干净， 返回从开始等到所有咖啡机变干净的最短时间 三个参数：int[] arr、int N，int a、int b

这个是去年京东的原题

其实该问题分为两个问题来解：

  1. N个人喝完咖啡时间最短的最优分配方案-->>使用小根堆实现调度算法每个咖啡机什么时间点可再用、制造咖啡所需时间
  2. 洗杯子的决策算法

暴力递归代码：

package class20;

import java.util.Comparator;
import java.util.PriorityQueue;

import class20.Code03_Coffee.Machine;
import class20.Code03_Coffee.MachineComparator;

/**
 * - 泡咖啡问题
 * - 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
 * - 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
 * - 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
 * - 每个人喝完之后咖啡，杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
 * - 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
 * - 四个参数：arr, n, a, b
 * - 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。
 * @author yangyanchao
 */
public class Test03_Coffee {
	
	/**
	 * 	咖啡机信息
	 * @author yangyanchao
	 *
	 */
	public static class CoffeeMachice {
		/**
		 * 	可再用的时间点
		 */
		public int reuse;
		/**
		 * 	制造时间
		 */
		public int time;
		
		public CoffeeMachice(int reuse, int time) {
			this.reuse = reuse;
			this.time = time;
		}
	}
	
	/**
	 * 	咖啡机的比较器
	 * @author yangyanchao
	 *
	 */
	public static class DrinkComparator implements Comparator<CoffeeMachice> {

		@Override
		public int compare(CoffeeMachice o1, CoffeeMachice o2) {
			return (o1.reuse + o1.time) - (o2.reuse + o2.time);
		}

	}
	
	
	/**
	 * - 泡咖啡问题 暴力递归版本
	 * @param arr
	 * @param N
	 * @param A
	 * @param B
	 * @return
	 */
	public static int coffee(int[] arr, int N, int A, int B) {
		if(N < 0 || A < 0 || B < 0 || arr == null || arr.length == 0) {
			return -1;
		}
		// 分配人员到咖啡机
		// 每个人最优的喝完时间点
		int[] drink = new int[N];
		// 使用贪心算法 咖啡机再用的时间点与咖啡机制造咖啡所需时间的对象入小根堆
		scheduling(arr, drink);
		// 洗杯子
		return process(drink, 0, 0, A, B);
	}



	/**
	 * 	洗杯子的选择策略递归
	 * @param drink
	 * @param index  当前的位置
	 * @param wash   洗机时间点可用
	 * @param a
	 * @param b
	 * @return
	 */
	private static int process(int[] drink, int index, int wash, int a, int b) {
		if(index == drink.length) {
			// 没有杯子要洗了
			return 0;
		}
		// 要么扔到咖啡机洗去
		int wash1 = Math.max(drink[index], wash) + a;
		int p1 = Math.max(wash1, process(drink, index + 1, wash1, a, b));
		// 要么蒸发去
		int p2 = Math.max(drink[index] + b, process(drink, index + 1, wash, a, b));
		return Math.min(p1, p2);
	}



	/**
	 * 	使用贪心算法 最优排队策略
	 * @param arr
	 * @param drink
	 */
	private static void scheduling(int[] arr, int[] drink) {
		// 小根堆
		PriorityQueue<CoffeeMachice> heap = new PriorityQueue<>(new DrinkComparator());
		for(int i = 0; i < arr.length; i++) {
			heap.add(new CoffeeMachice(0, arr[i]));
		}
		CoffeeMachice cm = null;
		for(int i = 0; i < drink.length; i++) {
			cm = heap.poll();
			drink[i] = cm.reuse + cm.time;
			cm.reuse = drink[i];
			heap.add(cm);
		}
	}
	
	// 优良一点的暴力尝试的方法
		public static int minTime1(int[] arr, int n, int a, int b) {
			PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
			for (int i = 0; i < arr.length; i++) {
				heap.add(new Machine(0, arr[i]));
			}
			int[] drinks = new int[n];
			for (int i = 0; i < n; i++) {
				Machine cur = heap.poll();
				cur.timePoint += cur.workTime;
				drinks[i] = cur.timePoint;
				heap.add(cur);
			}
			return bestTime(drinks, a, b, 0, 0);
		}

		// drinks 所有杯子可以开始洗的时间
		// wash 单杯洗干净的时间（串行）
		// air 挥发干净的时间(并行)
		// free 洗的机器什么时候可用
		// drinks[index.....]都变干净，最早的结束时间（返回）
		public static int bestTime(int[] drinks, int wash, int air, int index, int free) {
			if (index == drinks.length) {
				return 0;
			}
			// index号杯子 决定洗
			int selfClean1 = Math.max(drinks[index], free) + wash;
			int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1);
			int p1 = Math.max(selfClean1, restClean1);

			// index号杯子 决定挥发
			int selfClean2 = drinks[index] + air;
			int restClean2 = bestTime(drinks, wash, air, index + 1, free);
			int p2 = Math.max(selfClean2, restClean2);
			return Math.min(p1, p2);
		}
	
	// for test
		public static int[] randomArray(int len, int max) {
			int[] arr = new int[len];
			for (int i = 0; i < len; i++) {
				arr[i] = (int) (Math.random() * max) + 1;
			}
			return arr;
		}

		// for test
		public static void printArray(int[] arr) {
			System.out.print("arr : ");
			for (int j = 0; j < arr.length; j++) {
				System.out.print(arr[j] + ", ");
			}
			System.out.println();
		}

		public static void main(String[] args) {
			int len = 10;
			int max = 10;
			int testTime = 1000000;
			System.out.println("测试开始");
			for (int i = 0; i < testTime; i++) {
				int[] arr = randomArray(len, max);
				int n = (int) (Math.random() * 7) + 1;
				int a = (int) (Math.random() * 7) + 1;
				int b = (int) (Math.random() * 10) + 1;
				int ans1 = coffee(arr, n, a, b);
				int ans2 = minTime1(arr, n, a, b);
//				int ans3 = minTime2(arr, n, a, b); || ans2 != ans3
				if (ans1 != ans2) {
					printArray(arr);
					System.out.println("n : " + n);
					System.out.println("a : " + a);
					System.out.println("b : " + b);
//					System.out.println(ans1 + " , " + ans2 + " , " + ans3);
					System.out.println(ans1 + " , " + ans2);
					System.out.println("===============");
					break;
				}
			}
			System.out.println("测试结束");

		}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

动态规划代码：

  • 这里洗机的可用时间点似乎不太好确定边界，这时就得使用业务限制了
  • 洗机最大可用时间为每个人的杯子都拿去洗
package class20;

import java.util.Comparator;
import java.util.PriorityQueue;

import class20.Code03_Coffee.Machine;
import class20.Code03_Coffee.MachineComparator;

/**
 * - 泡咖啡问题
 * - 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
 * - 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
 * - 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
 * - 每个人喝完之后咖啡，杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
 * - 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
 * - 四个参数：arr, n, a, b
 * - 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。
 * @author yangyanchao
 */
public class Test03_Coffee {
	
	/**
	 * 	咖啡机信息
	 * @author yangyanchao
	 *
	 */
	public static class CoffeeMachice {
		/**
		 * 	可再用的时间点
		 */
		public int reuse;
		/**
		 * 	制造时间
		 */
		public int time;
		
		public CoffeeMachice(int reuse, int time) {
			this.reuse = reuse;
			this.time = time;
		}
	}
	
	/**
	 * 	咖啡机的比较器
	 * @author yangyanchao
	 *
	 */
	public static class DrinkComparator implements Comparator<CoffeeMachice> {

		@Override
		public int compare(CoffeeMachice o1, CoffeeMachice o2) {
			return (o1.reuse + o1.time) - (o2.reuse + o2.time);
		}

	}
	
	
	/**
	 * - 泡咖啡问题 暴力递归版本
	 * @param arr
	 * @param N
	 * @param A
	 * @param B
	 * @return
	 */
	public static int coffee(int[] arr, int N, int A, int B) {
		if(N < 0 || A < 0 || B < 0 || arr == null || arr.length == 0) {
			return -1;
		}
		// 分配人员到咖啡机
		// 每个人最优的喝完时间点
		int[] drink = new int[N];
		// 使用贪心算法 咖啡机再用的时间点与咖啡机制造咖啡所需时间的对象入小根堆
		scheduling(arr, drink);
		// 洗杯子
		return process(drink, 0, 0, A, B);
	}
	
	/**
	 * - 泡咖啡问题 动态规划版本
	 * @param arr
	 * @param N
	 * @param A
	 * @param B
	 * @return
	 */
	public static int coffeeDp(int[] arr, int N, int A, int B) {
		if(N < 0 || A < 0 || B < 0 || arr == null || arr.length == 0) {
			return -1;
		}
		// 分配人员到咖啡机
		// 每个人最优的喝完时间点
		int[] drink = new int[N];
		// 使用贪心算法 咖啡机再用的时间点与咖啡机制造咖啡所需时间的对象入小根堆
		scheduling(arr, drink);
		int maxWash = 0;
		// 这里洗机的可用时间点似乎不太好确定边界，这时就得使用业务限制了 
		// 洗机最大可用时间为每个人的杯子都拿去洗
		for(int i = 0; i < N; i++) {
			maxWash += Math.max(maxWash, drink[i]) + A;
		}
		// 洗杯子
		int[][] dp = new int[N + 1][maxWash + 1];
		// 最后一行是0 而且这行数据依赖于下一行数据则应该自下向上遍历
		for(int index = N - 1; index >= 0; index--) {
			for(int wash = 0; wash <= maxWash; wash++) {
				// 要么扔到咖啡机洗去
				int wash1 = Math.max(drink[index], wash) + A;
				if(wash1 > maxWash) {
					break;
				}
				int p1 = Math.max(wash1, dp[index + 1][wash1]);
				// 要么蒸发去
				int p2 = Math.max(drink[index] + B, dp[index + 1][wash]);
				dp[index][wash] = Math.min(p1, p2);
			}
		}
		return dp[0][0];
	}

	/**
	 * 	洗杯子的选择策略递归
	 * @param drink
	 * @param index  当前的位置
	 * @param wash   洗机时间点可用
	 * @param a
	 * @param b
	 * @return
	 */
	private static int process(int[] drink, int index, int wash, int a, int b) {
		if(index == drink.length) {
			// 没有杯子要洗了
			return 0;
		}
		// 要么扔到咖啡机洗去
		int wash1 = Math.max(drink[index], wash) + a;
		int p1 = Math.max(wash1, process(drink, index + 1, wash1, a, b));
		// 要么蒸发去
		int p2 = Math.max(drink[index] + b, process(drink, index + 1, wash, a, b));
		return Math.min(p1, p2);
	}



	/**
	 * 	使用贪心算法 最优排队策略
	 * @param arr
	 * @param drink
	 */
	private static void scheduling(int[] arr, int[] drink) {
		// 小根堆
		PriorityQueue<CoffeeMachice> heap = new PriorityQueue<>(new DrinkComparator());
		for(int i = 0; i < arr.length; i++) {
			heap.add(new CoffeeMachice(0, arr[i]));
		}
		CoffeeMachice cm = null;
		for(int i = 0; i < drink.length; i++) {
			cm = heap.poll();
			drink[i] = cm.reuse + cm.time;
			cm.reuse = drink[i];
			heap.add(cm);
		}
	}
	
	// 优良一点的暴力尝试的方法
		public static int minTime1(int[] arr, int n, int a, int b) {
			PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
			for (int i = 0; i < arr.length; i++) {
				heap.add(new Machine(0, arr[i]));
			}
			int[] drinks = new int[n];
			for (int i = 0; i < n; i++) {
				Machine cur = heap.poll();
				cur.timePoint += cur.workTime;
				drinks[i] = cur.timePoint;
				heap.add(cur);
			}
			return bestTime(drinks, a, b, 0, 0);
		}

		// drinks 所有杯子可以开始洗的时间
		// wash 单杯洗干净的时间（串行）
		// air 挥发干净的时间(并行)
		// free 洗的机器什么时候可用
		// drinks[index.....]都变干净，最早的结束时间（返回）
		public static int bestTime(int[] drinks, int wash, int air, int index, int free) {
			if (index == drinks.length) {
				return 0;
			}
			// index号杯子 决定洗
			int selfClean1 = Math.max(drinks[index], free) + wash;
			int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1);
			int p1 = Math.max(selfClean1, restClean1);

			// index号杯子 决定挥发
			int selfClean2 = drinks[index] + air;
			int restClean2 = bestTime(drinks, wash, air, index + 1, free);
			int p2 = Math.max(selfClean2, restClean2);
			return Math.min(p1, p2);
		}
	
		// for test
		public static int[] randomArray(int len, int max) {
			int[] arr = new int[len];
			for (int i = 0; i < len; i++) {
				arr[i] = (int) (Math.random() * max) + 1;
			}
			return arr;
		}

		// for test
		public static void printArray(int[] arr) {
			System.out.print("arr : ");
			for (int j = 0; j < arr.length; j++) {
				System.out.print(arr[j] + ", ");
			}
			System.out.println();
		}

		public static void main(String[] args) {
			int len = 10;
			int max = 10;
			int testTime = 1000000;
			System.out.println("测试开始");
			for (int i = 0; i < testTime; i++) {
				int[] arr = randomArray(len, max);
				int n = (int) (Math.random() * 7) + 1;
				int a = (int) (Math.random() * 7) + 1;
				int b = (int) (Math.random() * 10) + 1;
				int ans1 = coffee(arr, n, a, b);
				int ans2 = minTime1(arr, n, a, b);
				int ans3 = coffeeDp(arr, n, a, b); 
				if (ans1 != ans2 || ans2 != ans3) {
					printArray(arr);
					System.out.println("n : " + n);
					System.out.println("a : " + a);
					System.out.println("b : " + b);
					System.out.println(ans1 + " , " + ans2 + " , " + ans3);
					System.out.println("===============");
					break;
				}
			}
			System.out.println("测试结束");

		}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248

# 课程练习

# 练习一

机器人行进问题的动态规划

范围上的尝试模型

假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个) 如果机器人来到1位置，那么下一步只能往右来到2位置； 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置； 如果机器人来到中间位置，那么下一步可以往左走或者往右走； 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种 给定四个参数 N、M、K、P，返回方法数。

练习代码：

package class20;

/**
 * - 机器人行进问题的动态规划
 * - 范围上的尝试模型
 * - 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
 * - 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
 * - 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * - 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
 * - 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * - 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * - 给定四个参数 N、M、K、P，返回方法数。
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	dp-动态规划
 *  cp-比较器
 */
public class Practice01 {
	
	public static int cp(int N, int start, int aim, int K) {
		if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
			return -1;
		}
		return process1(start, K, aim, N);
	}

	public static int process1(int cur, int rest, int aim, int N) {
		if (rest == 0) { // 如果已经不需要走了，走完了！
			return cur == aim ? 1 : 0;
		}
		// (cur, rest)
		if (cur == 1) { // 1 -> 2
			return process1(2, rest - 1, aim, N);
		}
		// (cur, rest)
		if (cur == N) { // N-1 <- N
			return process1(N - 1, rest - 1, aim, N);
		}
		// (cur, rest)
		return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
	}
	
	public static int vr(int N, int M, int P, int K) {
		if(N < 2 || M < 1 || M > N || P < 1 || P > N || K < 1) {
			return -1;
		}
		return vrProcess(N, P, M, K);
	}
	
	/**
	 * 	当前位置index到目标位置target还剩余rest步的情况下的方法数
	 * @param N       位置数
	 * @param target  目标位置
	 * @param index   当前位置
	 * @param rest    剩余步数
	 * @return
	 */
	public static int vrProcess(int N, int target, int index, int rest) {
		if(rest == 0) {
			return index == target ? 1 : 0;
		}
		// 如果机器人来到1位置，那么下一步只能往右来到2位置；
		if(index == 1) {
			return vrProcess(N, target, 2, rest - 1);
		}
		// 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
		if(index == N) {
			return vrProcess(N, target, N - 1, rest - 1);
		}
		// 如果机器人来到中间位置，那么下一步可以往左走或者往右走
		return vrProcess(N, target, index - 1, rest - 1) + vrProcess(N, target, index + 1, rest - 1);
	}
	
	public static int dp(int N, int M, int P, int K) {
		if(N < 2 || M < 1 || M > N || P < 1 || P > N || K < 1) {
			return -1;
		}
		int[][] dp = new int[N + 1][K + 1];
		dp[P][0] = 1;
		for(int rest = 1; rest <= K; rest++) {
			dp[1][rest] = dp[2][rest - 1];
			for(int index = 2; index <= N - 1; index++) {
				dp[index][rest] = dp[index - 1][rest - 1] + dp[index + 1][rest - 1];
			}
			dp[N][rest] = dp[N - 1][rest - 1];
		}
		return dp[M][K];
	}
	
	public static void main(String[] args) {
		System.out.println(cp(5, 2, 4, 6));
		System.out.println(vr(5, 2, 4, 6));
		System.out.println(dp(5, 2, 4, 6));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

# 练习二

纸牌问题

范围上的尝试模型

给定一个整型数组arr，代表数值不同的纸牌排成一条线 玩家A和玩家B依次拿走每张纸牌 规定玩家A先拿，玩家B后拿 但是每个玩家每次只能拿走最左或最右的纸牌 玩家A和玩家B都绝顶聪明 请返回最后获胜者的分数。

分为先手与后手，拿走纸牌获得牌值分数，返回先手与后手情况下的最大分数

练习代码：

package class20;
/**
 * - 纸牌问题
 * - 范围上的尝试模型
 * - 给定一个整型数组arr，代表数值不同的纸牌排成一条线
 * - 玩家A和玩家B依次拿走每张纸牌
 * - 规定玩家A先拿，玩家B后拿
 * - 但是每个玩家每次只能拿走最左或最右的纸牌
 * - 玩家A和玩家B都绝顶聪明
 * - 请返回最后获胜者的分数。
 * - 分为先手与后手，拿走纸牌获得牌值分数，返回先手与后手情况下的最大分数
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	dp-动态规划
 *	cp-比较器
 */
public class Practice02 {
	
	// 根据规则，返回获胜者的分数
	public static int cp(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int first = f1(arr, 0, arr.length - 1);
		int second = g1(arr, 0, arr.length - 1);
		return Math.max(first, second);
	}

	// arr[L..R]，先手获得的最好分数返回
	public static int f1(int[] arr, int L, int R) {
		if (L == R) {
			return arr[L];
		}
		int p1 = arr[L] + g1(arr, L + 1, R);
		int p2 = arr[R] + g1(arr, L, R - 1);
		return Math.max(p1, p2);
	}

	// // arr[L..R]，后手获得的最好分数返回
	public static int g1(int[] arr, int L, int R) {
		if (L == R) {
			return 0;
		}
		int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
		int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
		return Math.min(p1, p2);
	}
	
	public static int vr(int[] arr) {
		if(arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		// 先手情况
		int p1 = f(arr , 0, N - 1);
		// 后手情况
		int p2 = g(arr , 0, N - 1);
		return Math.max(p1, p2);
	}

	private static int f(int[] arr, int L, int R) {
		// 先手情况
		if(L == R) {
			return arr[L];
		}
		// 先手拿左 后手要在L + 1 ... R上选择了
		int p1 = arr[L] + g(arr, L + 1, R);
		// 先手拿右 后手要在L ... R - 1上选择了
		int p2 = arr[R] + g(arr, L, R - 1);
		return Math.max(p1, p2);
	}

	private static int g(int[] arr, int L, int R) {
		// 后手情况
		if(L == R) {
			// 当只有一个时轮不到自己选啊
			return 0;
		}
		// 先手拿左 后手要努力在L + 1 ... R上选择最大的分数
		int p1 = f(arr, L + 1, R);
		// 先手拿右 后手要努力在L ... R - 1上选择最大的分数
		int p2 = f(arr, L, R - 1);
		// 因为先手绝顶聪明不会将大的分数给到后手的 所以是两者取最小值
		return Math.min(p1, p2);
	}
	
	public static int dp(int[] arr) {
		if(arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] fdp = new int[N][N];
		int[][] gdp = new int[N][N];
		for(int i = 0; i < N; i++) {
			fdp[i][i] = arr[i];
			gdp[i][i] = 0;
		}
		for(int i = 1; i < N; i++) {
			int L = 0;
			int R = i;
			while(R < N) {
				fdp[L][R] = Math.max(arr[L] + gdp[L + 1][R], arr[R] + gdp[L][R - 1]);
				gdp[L][R] = Math.min(fdp[L + 1][R], fdp[L][R - 1]);
				L++;
				R++;
			}
		}
		// 先手情况
		int p1 = fdp[0][N - 1];
		// 后手情况
		int p2 = gdp[0][N - 1];
		return Math.max(p1, p2);
	}
	
	public static void main(String[] args) {
		int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
		System.out.println(cp(arr));
		System.out.println(vr(arr));
		System.out.println(dp(arr));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

# 练习三

背包问题

从左往右的尝试模型

给定两个长度都为N的数组weights和values， weights[i]和values[i]分别代表 i号物品的重量和价值。 给定一个正数bag，表示一个载重bag的袋子， 你装的物品不能超过这个重量。 返回你能装下最多的价值是多少?

练习代码：

package class20;
/**
 * - 背包问题
 * - 从左往右的尝试模型
 * - 给定两个长度都为N的数组weights和values，
 * - weights[i]和values[i]分别代表 i号物品的重量和价值。
 * - 给定一个正数bag，表示一个载重bag的袋子，
 * - 你装的物品不能超过这个重量。
 * - 返回你能装下最多的价值是多少? 
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	dp-动态规划
 *	cp-比较器
 */
public class Practice03 {
	public static int vr(int[] weights, int[] values, int bag) {
		if(bag < 0 || weights == null || weights.length == 0 || values == null 
				|| values.length == 0 || weights.length != values.length) {
			return -1;
		}
		return vrProcess(weights, values, 0, bag);
	}
	public static int vrProcess(int[] weights, int[] values, int index, int rest) {
		if(rest < 0) {
			return -1;
		}
		if(index == weights.length) {
			return 0;
		}
		// 要index位置的物品
		int p1 = vrProcess(weights, values, index + 1, rest - weights[index]);
		p1 = p1 == -1 ? 0 : values[index] + p1;
		// 不要index位置的物品
		int p2 = vrProcess(weights, values, index + 1, rest);
		return Math.max(p1, p2);
	}
	
	public static int dp(int[] weights, int[] values, int bag) {
		if(bag < 0 || weights == null || values == null 
				|| values.length == 0 || weights.length != values.length) {
			return 0;
		}
		int N = weights.length;
		int[][] dp = new int[N + 1][bag + 1];
		for(int i = 0; i <= bag; i++) {
			dp[N][i] = 0;
		}
		for(int index = N - 1; index >= 0; index--) {
			for(int rest = 0; rest <= bag; rest++) {
				// 要index位置的物品
				int p1 = 0;
				if(rest - weights[index] >= 0) {
					p1 = values[index] + dp[index + 1][rest - weights[index]];
				}
				// 不要index位置的物品
				int p2 = dp[index + 1][rest];
				dp[index][rest] =  Math.max(p1, p2);
			}
		}
		return dp[0][bag];
	}
	
	public static int cp(int[] w, int[] v, int bag) {
		if (w == null || v == null || w.length != v.length || w.length == 0) {
			return 0;
		}
		return process(w, v, 0, bag);
	}

	public static int process(int[] w, int[] v, int index, int rest) {
		if (rest < 0) {
			return -1;
		}
		if (index == w.length) {
			return 0;
		}
		int p1 = process(w, v, index + 1, rest);
		int p2 = 0;
		int next = process(w, v, index + 1, rest - w[index]);
		if (next != -1) {
			p2 = v[index] + next;
		}
		return Math.max(p1, p2);
	}
	
	public static void main(String[] args) {
		int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
		int[] values = { 5, 6, 3, 19, 12, 4, 2 };
		int bag = 15;
		System.out.println(cp(weights, values, bag));
		System.out.println(vr(weights, values, bag));
		System.out.println(dp(weights, values, bag));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

# 练习四

数字串转化为字符串问题

从左往右的尝试模型

规定1和A对应、2和B对应、3和C对应...26和Z对应 那么一个数字字符串比如"111”就可以转化为: "AAA"、"KA"和"AK" 给定一个只有数字字符组成的字符串str，返回有多少种转化结果

练习代码：

package class20;
/**
 * - 数字串转化为字符串问题
 * - 从左往右的尝试模型
 * - 规定1和A对应、2和B对应、3和C对应...26和Z对应
 * - 那么一个数字字符串比如"111”就可以转化为:
 * - "AAA"、"KA"和"AK"
 * - 给定一个只有数字字符组成的字符串str，返回有多少种转化结果 
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	dp-动态规划
 *	cp-比较器
 */
public class Practice04 {
	
	public static int cp(String str) {
		if (str == null || str.length() == 0) {
			return 0;
		}
		return process(str.toCharArray(), 0);
	}

	public static int process(char[] str, int i) {
		if (i == str.length) {
			return 1;
		}
		if (str[i] == '0') {
			return 0;
		}
		int ways = process(str, i + 1);
		if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
			ways += process(str, i + 2);
		}
		return ways;
	}
	
	public static int vr(String numStr) {
		if(numStr == null || numStr.length() == 0) {
			return 0;
		}
		char[] str = numStr.toCharArray();
		return vrProcess(str, 0);
	}

	/**
	 * 	当前位置index下字符序列str[index...],返回多少种转化结果
	 * @param str
	 * @param index  当前位置
	 * @return
	 */
	private static int vrProcess(char[] str, int index) {
		if(index == str.length) {
			// 当前位置能来到最后说明前序方法中是有效的
			return 1;
		}
		if(str[index] == '0') {
			// 如果当前位置是'0'字符 则没有任何转化的方法
			return 0;
		}
		// 要当前位置index
		int p1 = vrProcess(str, index + 1);
		// 不要当前位置index
		int p2 = index + 1 < str.length && (str[index] - '0') * 10 + (str[index + 1] - '0') < 27 ? vrProcess(str, index + 2) : 0;
		return p1 + p2;
	}
	
	public static int dp(String numStr) {
		if(numStr == null || numStr.length() == 0) {
			return 0;
		}
		char[] str = numStr.toCharArray();
		int N = str.length;
		int[] dp = new int[N + 1];
		dp[N] = 1;
		for(int index = N - 1; index >= 0; index--) {
			if(str[index] != '0') {
				int p1 = dp[index + 1];
				int p2 = index + 1 < str.length && (str[index] - '0') * 10 + (str[index + 1] - '0') < 27 ? dp[index + 2] : 0;
				dp[index] =  p1 + p2;
			}
		}
		return dp[0];
	}
	
	public static void main(String[] args) {
		System.out.println(cp("7210231231232031203123"));
		System.out.println(vr("7210231231232031203123"));
		System.out.println(dp("7210231231232031203123"));
		
		System.out.println(cp("305"));
		System.out.println(vr("305"));
		System.out.println(dp("305"));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

# 练习五

贴纸问题

从左往右的尝试模型

给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文 arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来 返回需要至少多少张贴纸可以完成这个任务。 例子：str= "babac"，arr = {"ba","c","abcd"} ba + ba + c 3 abcd + abcd 2 abcd+ba 2 所以返回2

练习代码：

package class20;

import java.util.HashMap;

/**
 * - 本题测试链接：https://leetcode.com/problems/stickers-to-spell-word
 * -贴纸问题
 * -给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
 * -arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
 * -返回需要至少多少张贴纸可以完成这个任务。
 * -例子：str= "babac"，arr = {"ba","c","abcd"}
 * -ba + ba + c  3  abcd + abcd 2  abcd+ba 2
 * -所以返回2 	
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	ms-记忆搜索
 *	cp-比较器
 */
public class Practice05 {
	public static int vr(String[] arr, String targetStr) {
		if(targetStr == null || targetStr.length() == 0 || arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] arrCp = new int[N][26];
		for(int i = 0; i < N; i++) {
			char[] str1 = arr[i].toCharArray();
			for(char cha : str1) {
				arrCp[i][cha - 'a']++;
			}
		}
		// arr 使用词频代替
		int ans = vrProcess(arrCp, targetStr);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	/**
	 * 	rest字符串使用至少多少张贴纸
	 * @param arrCp 
	 * @param rest
	 * @return
	 */
	private static int vrProcess(int[][] arrCp, String rest) {
		if(rest.length() == 0) {
			return 0;
		}
		// restStr 使用词频代替
		char[] str = rest.toCharArray();
		int[] restCp = new int[26];
		for(char cha : str) {
			restCp[cha - 'a']++;
		}
		int N = arrCp.length;
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < N; i++) {
			// 最关键的优化(重要的剪枝!这一步也是贪心!)
			if(arrCp[i][str[0] - 'a'] > 0) {
				StringBuilder sb = new StringBuilder();
				for(int k = 0; k < 26; k++) {
					if(restCp[k] > 0) {
						int nums = restCp[k] - arrCp[i][k];
						for(int m = 0; m < nums; m++) {
							sb.append((char)('a' + k));
						}
					}
				}
				min = Math.min(min, vrProcess(arrCp, sb.toString()));
			}
		}
		return min + (min == Integer.MAX_VALUE ? 0 : 1);
	}
	
	public static int ms(String[] arr, String targetStr) {
		if(targetStr == null || targetStr.length() == 0 || arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] arrCp = new int[N][26];
		for(int i = 0; i < N; i++) {
			char[] str1 = arr[i].toCharArray();
			for(char cha : str1) {
				arrCp[i][cha - 'a']++;
			}
		}
		HashMap<String, Integer> map = new HashMap<>();
		map.put("", 0);
		// arr 使用词频代替
		int ans = msProcess(arrCp, targetStr, map);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	private static int msProcess(int[][] arrCp, String rest, HashMap<String, Integer> map) {
		if(map.containsKey(rest)) {
			return map.get(rest);
		}
		// restStr 使用词频代替
		char[] str = rest.toCharArray();
		int[] restCp = new int[26];
		for(char cha : str) {
			restCp[cha - 'a']++;
		}
		int N = arrCp.length;
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < N; i++) {
			// 最关键的优化(重要的剪枝!这一步也是贪心!)
			if(arrCp[i][str[0] - 'a'] > 0) {
				StringBuilder sb = new StringBuilder();
				for(int k = 0; k < 26; k++) {
					if(restCp[k] > 0) {
						int nums = restCp[k] - arrCp[i][k];
						for(int m = 0; m < nums; m++) {
							sb.append((char)('a' + k));
						}
					}
				}
				min = Math.min(min, msProcess(arrCp, sb.toString(), map));
			}
		}
		int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
		map.put(rest, ans);
		return ans;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

# 练习六

最长公共子序列问题

多样本位置全对应的尝试模型

给定两个字符串str1和str2， 返回这两个字符串的最长公共子序列长度

比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k” 最长公共子序列是“123456”，所以返回长度6

练习代码：

package class20;
/**
 *- 链接：https://leetcode.com/problems/longest-common-subsequence/
 *- 最长公共子序列问题
 *- 给定两个字符串str1和str2，
 *- 返回这两个字符串的最长公共子序列长度
 *- 比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
 *- 最长公共子序列是“123456”，所以返回长度6
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	dp-动态规划
 *	cp-比较器
 */
public class Practice06 {
	public static int vr(String s1, String s2) {
		if(s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
			return 0;
		}
		char[] str1 = s1.toCharArray();
		int N1 = str1.length;
		char[] str2 = s2.toCharArray();
		int N2 = str2.length;
		return vrProcess(str1, str2, N1 - 1, N2 - 1);
	}

	private static int vrProcess(char[] str1, char[] str2, int index1, int index2) {
		// 公共子序列是等于1 的basecase
		if(index1 == 0 && index2 == 0) {
			return str1[index1] == str2[index2] ? 1 : 0;
		}
		if(index1 == 0) {
			return str1[index1] == str2[index2] ? 1 : vrProcess(str1, str2, index1, index2 - 1);
		}
		if(index2 == 0) {
			return str2[index2] == str1[index1] ? 1 : vrProcess(str1, str2, index1 - 1, index2);
		}
		// 公共子序列是大于1 的
		// 要么公共子序列不是index1结尾，有可能index2结尾
		int p1 = vrProcess(str1, str2, index1 - 1, index2);
		// 要么公共子序列不是index2结尾，有可能index1结尾
		int p2 = vrProcess(str1, str2, index1, index2 - 1);
		// 要么公共子序列必须是index12结尾，必须是index21结尾
		int p3 = str1[index1] == str2[index2] ? 1 + vrProcess(str1, str2, index1 - 1, index2 - 1) : 0;
		return Math.max(p1, Math.max(p2, p3));
	}
	
	public static int dp(String s1, String s2) {
		if(s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
			return 0;
		}
		char[] str1 = s1.toCharArray();
		int N1 = str1.length;
		char[] str2 = s2.toCharArray();
		int N2 = str2.length;
		int[][] dp = new int[N1][N2];
		dp[0][0] = str1[0] == str2[0] ? 1 : 0;
		for(int i = 1; i < N2; i++) {
			dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i - 1];
		}
		for(int i = 1; i < N1; i++) {
			dp[i][0] = str2[0] == str1[i] ? 1 : dp[i - 1][0];
		}
		for(int index1 = 1; index1 < N1; index1++) {
			for(int index2 = 1; index2 < N2; index2++) {
				int p1 = dp[index1 - 1][index2];
				int p2 = dp[index1][index2 - 1];
				int p3 = str1[index1] == str2[index2] ? 1 + dp[index1 - 1][index2 - 1] : 0;
				dp[index1][index2] = Math.max(p1, Math.max(p2, p3));
			}
		}
		return dp[N1 - 1][N2 - 1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

# 练习七

最长回文子序列

给定一个字符串str，返回这个字符串的最长回文子序列长度 比如 ： str = “a12b3c43def2ghi1kpm” 最长回文子序列是“1234321”或者“123c321”，返回长度7

练习代码：

package class20;
/**
 * - 测试链接：https://leetcode.com/problems/longest-palindromic-subsequence/
 * - 最长回文子序列
 * - 给定一个字符串str，返回这个字符串的最长回文子序列长度
 * - 比如 ： str = “a12b3c43def2ghi1kpm”
 * - 最长回文子序列是“1234321”或者“123c321”，返回长度7
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	dp-动态规划
 *	cp-比较器
 */
public class Practice07 {
	public int vr(String s) {
		if(s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		return vrProcess(str, 0, N - 1);
    }

	private int vrProcess(char[] str, int L, int R) {
		if(L == R) {
			return 1;
		}
		if(L == R - 1) {
			return str[L] == str[R] ? 2 : 1;
		}
		// 回文子序列不以L开头，不以R结尾
		int p1 = vrProcess(str, L + 1, R - 1);
		// 回文子序列以L开头，不以R结尾
		int p2 = vrProcess(str, L, R - 1);
		// 回文子序列不以L开头，以R结尾
		int p3 = vrProcess(str, L + 1, R);
		// 回文子序列以L开头，以R结尾
		int p4 = str[L] == str[R] ? 2 + vrProcess(str, L + 1, R - 1) : 0;
		return Math.max(Math.max(p1, p2), Math.max(p3, p4));
	}
	
	public int dp(String s) {
		if(s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		int[][] dp = new int[N][N];
		dp[0][0] = 1;
		for(int i = 1; i < N; i++) {
			dp[i - 1][i - 1] = 1;
			dp[i - 1][i] = str[i - 1] == str[i] ? 2 : 1;
		}
		int startR = N - 1;
		int R = 0;
		for(int L = N - 3; L >= 0; L--) {
			R = startR;
			while(R < N) {
				int p2 = dp[L][R - 1];
				int p3 = dp[L + 1][R];
				int p4 = str[L] == str[R] ? 2 + dp[L + 1][R - 1] : 0;
				dp[L][R] = Math.max(p2, Math.max(p3, p4));
				R++;
			}
			startR--;
		}
		return dp[0][N - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

# 练习八

象棋走马问题

请同学们自行搜索或者想象一个象棋的棋盘， 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域 给你三个 参数 x，y，k 返回“马”从(0,0)位置出发，必须走k步 最后落在(x,y)上的方法数有多少种?

练习代码：

package class20;
/**
 * - 象棋走马问题
 * - 请同学们自行搜索或者想象一个象棋的棋盘，
 * - 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
 * - 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
 * - 给你三个 参数 x，y，k
 * - 返回“马”从(0,0)位置出发，必须走k步
 * - 最后落在(x,y)上的方法数有多少种?
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	dp-动态规划
 *	cp-比较器
 */
public class Practice08 {
	
	public static int dp(int a, int b, int k) {
		if(a > 8 || b > 9 || a < 0 || b < 0 || k < 1) {
			return -1;
		}
		int[][][] dp = new int[9][10][k + 1];
		dp[a][b][0] = 1;
		for(int step = 1; step <= k; step++) {
			for(int x = 0; x < 9; x++) {
				for(int y = 0; y < 10; y++) {
					dp[x][y][step] += pick(dp, x + 2, y + 1, step - 1);
					dp[x][y][step] += pick(dp, x + 1, y + 2, step - 1);
					dp[x][y][step] += pick(dp, x - 1, y + 2, step - 1);
					dp[x][y][step] += pick(dp, x - 2, y + 1, step - 1);
					dp[x][y][step] += pick(dp, x + 2, y - 1, step - 1);
					dp[x][y][step] += pick(dp, x + 1, y - 2, step - 1);
					dp[x][y][step] += pick(dp, x - 1, y - 2, step - 1);
					dp[x][y][step] += pick(dp, x - 2, y - 1, step - 1);
				}
			}
		}
		return dp[0][0][k];
	}
	
	private static int pick(int[][][] dp, int x, int y, int k) {
		if(x > 8 || y > 9 || x < 0 || y < 0 ) {
			return 0;
		}
		return dp[x][y][k];
	}

	public static int vr(int a, int b, int k) {
		if(a > 8 || b > 9 || a < 0 || b < 0 || k < 1) {
			return -1;
		}
		return vrProcess(a, b, 0, 0, k);
	}

	private static int vrProcess(int a, int b, int x, int y, int k) {
		if(x > 8 || y > 9 || x < 0 || y < 0 ) {
			return 0;
		}
		if(k == 0) {
			return x == a && y == b ? 1 : 0;
		}
		int ways = 0;
		ways += vrProcess(a, b, x + 2, y + 1, k - 1);
		ways += vrProcess(a, b, x + 1, y + 2, k - 1);
		ways += vrProcess(a, b, x - 1, y + 2, k - 1);
		ways += vrProcess(a, b, x - 2, y + 1, k - 1);
		ways += vrProcess(a, b, x + 2, y - 1, k - 1);
		ways += vrProcess(a, b, x + 1, y - 2, k - 1);
		ways += vrProcess(a, b, x - 1, y - 2, k - 1);
		ways += vrProcess(a, b, x - 2, y - 1, k - 1);
		return ways;
	}
	
	public static int cp(int a, int b, int k) {
		if(a > 8 || b > 9 || k < 1) {
			return -1;
		}
		return process(0, 0, a, b, k);
	}

	private static int process(int x, int y, int a, int b, int rest) {
		if(x < 0 || y < 0 || x > 8 || y > 9) {
			// 马走偏了 0种可能
			return 0;
		}
		if(rest == 0) {
			// 剩余步数是0步
			// 若是正好走到了(a,b)点则返回1
			// 若不是则返回0
			return (x == a && y == b) ? 1 : 0;
		}
		// 1)马走左上立日(x+1,y+2)
		int ways = process(x + 1, y + 2, a, b, rest - 1);
		// 2)马走右上立日(x-1,y+2)
		ways += process(x - 1, y + 2, a, b, rest - 1);
		// 3)马走左上倒日(x+2,y+1)
		ways += process(x + 2, y + 1, a, b, rest - 1);
		// 4)马走右上倒日(x-2,y+1)
		ways += process(x - 2, y + 1, a, b, rest - 1);
		// 5)马走左下立日(x+1,y-2)
		ways += process(x + 1, y - 2, a, b, rest - 1);
		// 6)马走右下立日(x-1,y-2)
		ways += process(x - 1, y - 2, a, b, rest - 1);
		// 7)马走左下倒日(x+2,y-1)
		ways += process(x + 2, y - 1, a, b, rest - 1);
		// 8)马走右下倒日(x-2,y-1)
		ways += process(x - 2, y - 1, a, b, rest - 1);
		return ways;
	}
	
	public static void main(String[] args) {
		int x = 7;
		int y = 7;
		int step = 10;
		// 515813
		System.out.println(cp(x, y, step));
		System.out.println(vr(x, y, step));
		System.out.println(dp(x, y, step));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

# 练习九

泡咖啡问题

给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间 给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡 只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯 每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发 假设所有人拿到咖啡之后立刻喝干净， 返回从开始等到所有咖啡机变干净的最短时间 三个参数：int[] arr、int N，int a、int b

这个是去年京东的原题

其实该问题分为两个问题来解：

  1. N个人喝完咖啡时间最短的最优分配方案-->>使用小根堆实现调度算法每个咖啡机什么时间点可再用、制造咖啡所需时间
  2. 洗杯子的决策算法

练习代码：

package class20;

import java.util.Comparator;
import java.util.PriorityQueue;

import class20.Code03_Coffee.Machine;
import class20.Code03_Coffee.MachineComparator;

/**
 * - 泡咖啡问题
 * - 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
 * - 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
 * - 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
 * - 每个人喝完之后咖啡，杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
 * - 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
 * - 四个参数：arr, n, a, b
 * - 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。
 * @author yangyanchao
 *	函数
 *	vr-暴力递归
 *	dp-动态规划
 *	cp-比较器
 */
public class Practice09 {
	
	/**
	 * 	咖啡机信息
	 * @author yangyanchao
	 *
	 */
	public static class CoffeeMachice {
		/**
		 * 	可再用的时间点
		 */
		public int reuse;
		/**
		 * 	制造时间
		 */
		public int time;
		
		public CoffeeMachice(int reuse, int time) {
			this.reuse = reuse;
			this.time = time;
		}
	}
	
	/**
	 * 	咖啡机的比较器
	 * @author yangyanchao
	 *
	 */
	public static class DrinkComparator implements Comparator<CoffeeMachice> {

		@Override
		public int compare(CoffeeMachice o1, CoffeeMachice o2) {
			return (o1.reuse + o1.time) - (o2.reuse + o2.time);
		}

	}
	
	
	private static int vr(int[] arr, int n, int a, int b) {
		PriorityQueue<CoffeeMachice> heap = new PriorityQueue<>(new DrinkComparator());
		for(int i = 0; i < arr.length; i++) {
			heap.add(new CoffeeMachice(0, arr[i]));
		}
		int[] drink = new int[n];
		CoffeeMachice cur = null;
		for(int i = 0; i < drink.length; i++) {
			cur = heap.poll();
			cur.reuse += cur.time;
			drink[i] = cur.reuse;
			heap.add(cur);
		}
		return process(drink, a, b, 0, 0);
	}
	
	/**
	 * 	暴力递归版本
	 * @param arr
	 * @param a
	 * @param b
	 * @param index
	 * @param free
	 * @return
	 */
	private static int process(int[] drink, int a, int b, int index, int free) {
		if(index == drink.length) {
			// 杯子没了 所需时间为0
			return 0;
		}
		// 要么去洗机里洗
		int selfWashTime = Math.max(free, drink[index]) + a;
		int restWashTime = process(drink, a, b, index + 1, selfWashTime);
		int p1 = Math.max(selfWashTime, restWashTime);
		// 要么去挥发
		int p2 = Math.max(drink[index] + b, process(drink, a, b, index + 1, free));
		return Math.min(p1, p2);
	}
	
	private static int dp(int[] arr, int n, int a, int b) {
		PriorityQueue<CoffeeMachice> heap = new PriorityQueue<>(new DrinkComparator());
		for(int i = 0; i < arr.length; i++) {
			heap.add(new CoffeeMachice(0, arr[i]));
		}
		int[] drink = new int[n];
		CoffeeMachice cur = null;
		for(int i = 0; i < drink.length; i++) {
			cur = heap.poll();
			cur.reuse += cur.time;
			drink[i] = cur.reuse;
			heap.add(cur);
		}
		int maxFree = 0;
		for(int i = 0; i < drink.length; i++) {
			maxFree += Math.max(maxFree, drink[i]) + a;
		}
		int[][] dp = new int[n + 1][maxFree + 1];
		// 最后行是0 而且是该行依赖下行数据
		for(int index = n - 1; index >= 0; index--) {
			for(int free = 0; free <= maxFree; free++) {
				int selfWashTime = Math.max(free, drink[index]) + a;
				if(selfWashTime > maxFree) {
					break;
				}
				int restWashTime = dp[index + 1][selfWashTime];
				int p1 = Math.max(selfWashTime, restWashTime);
				// 要么去挥发
				int p2 = Math.max(drink[index] + b, dp[index + 1][free]);
				dp[index][free] = Math.min(p1, p2);
			}
		}
		return dp[0][0];
	}
	
	// 优良一点的暴力尝试的方法
	public static int cp(int[] arr, int n, int a, int b) {
		PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
		for (int i = 0; i < arr.length; i++) {
			heap.add(new Machine(0, arr[i]));
		}
		int[] drinks = new int[n];
		for (int i = 0; i < n; i++) {
			Machine cur = heap.poll();
			cur.timePoint += cur.workTime;
			drinks[i] = cur.timePoint;
			heap.add(cur);
		}
		return bestTime(drinks, a, b, 0, 0);
	}

	// drinks 所有杯子可以开始洗的时间
	// wash 单杯洗干净的时间（串行）
	// air 挥发干净的时间(并行)
	// free 洗的机器什么时候可用
	// drinks[index.....]都变干净，最早的结束时间（返回）
	public static int bestTime(int[] drinks, int wash, int air, int index, int free) {
		if (index == drinks.length) {
			return 0;
		}
		// index号杯子 决定洗
		int selfClean1 = Math.max(drinks[index], free) + wash;
		int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1);
		int p1 = Math.max(selfClean1, restClean1);

		// index号杯子 决定挥发
		int selfClean2 = drinks[index] + air;
		int restClean2 = bestTime(drinks, wash, air, index + 1, free);
		int p2 = Math.max(selfClean2, restClean2);
		return Math.min(p1, p2);
	}

	public static void main(String[] args) {
		int len = 10;
		int max = 10;
		int testTimes = 1000000;
		System.out.println("测试开始");
		for(int i = 0; i < testTimes; i++) {
			int[] arr = generateRandomArray(len, max);
			int n = (int) (Math.random() * 7) + 1;
			int a = (int) (Math.random() * 7) + 1;
			int b = (int) (Math.random() * 10) + 1;
			int ans1 = cp(arr, n, a, b);
			int ans2 = vr(arr, n, a, b);
			int ans3 = dp(arr, n, a, b); 
			if (ans1 != ans2 || ans2 != ans3) {
				printArray(arr);
				System.out.println("n : " + n);
				System.out.println("a : " + a);
				System.out.println("b : " + b);
				System.out.println(ans1 + " , " + ans2 + " , " + ans3);
				System.out.println("===============");
				break;
			}
			
		}
		System.out.println("测试结束");
	}
	
	// for test
	private static int[] generateRandomArray(int len, int max) {
		int[] arr = new int[len];
		for(int i = 0; i < arr.length; i++) {
			arr[i] = (int)(Math.random() * max) + 1;
		}
		return arr;
	}
	// for test
	public static void printArray(int[] arr) {
		System.out.print("arr : ");
		for (int j = 0; j < arr.length; j++) {
			System.out.print(arr[j] + ", ");
		}
		System.out.println();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217

← 第21节 暴力递归到动态规划（四） →