ARTS-第18周

发表于

ARTS （第18周）

想要真正的掌握，就应该多练多用多想。

本周：

动态规划

Algorithm 算法

凑单问题-所有情况的罗列

凑单问题：罗列全部的情况

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
package dynamic_programming;

import java.util.Arrays;
import java.util.LinkedList;

public class DpMoneyTest {
	public static void main(String[] args) {
		// while (true) {
		testMoney();
		// }

	}

	public static void testMoney() {
		int[] a = new int[15];
		for (int i = 0; i < a.length; i++) {
			a[i] = (int) (Math.random() * 10) + 1;
		}
		int p = (int) (Math.random() * 50 + 25);
		// a[0] = 101;
		// a[1] = 55;
		// p = 100;
		System.out.println(p + ":" + Arrays.toString(a));
		getMoney(a, p, 2);

	}

	public static void getMoney(int[] it, int p, int max) {
		int p2 = p * max;
		int len = it.length;
		boolean[][] t = new boolean[len][p2];
		t[0][0] = true;
		if (it[0] <= len) {
			t[0][it[0]] = true;
		}
		for (int i = 1; i < len; i++) {
			for (int j = 0; j < p2; j++) {
				t[i][j] = t[i - 1][j];
			}
			for (int j = 0; j + it[i] < p2; j++) {
				if (t[i - 1][j]) {
					t[i][j + it[i]] = true;
				}
			}

		}
		int r = -1;
		for (int i = p; i < p2; i++) {
			if (t[t.length - 1][i] == true) {
				r = i;
				break;
			}
		}
		if (r == -1) {
			System.out.println("没有");
			return;
		}
		System.out.println("有：" + r);

		System.out.println("不放的角度解析A========");
		print2(t, r, it);
		System.out.println("不放的角度解析B========");
		print3(t, r, it);
		System.out.println("放的角度解析========");
		print1(t, r, it);
		System.out.println("放和不放的混合解析========");
		LinkedList<Integer> list = new LinkedList<Integer>();
		printAll(t, r, it, it.length - 1, 0, list, r);
	}

	private static void printAll(boolean[][] t, int r, int[] it, int i, int level, LinkedList<Integer> list,
			int total) {

		if (i == 0) {
			if (r != 0) {
				// 最后个物品的判断
				// System.out.println("第" + 0 + "个物品,价钱" + it[0]);
				list.add(0);
			}
			// System.out.println("into:" + list);
			int validate = 0;
			for (Integer ix : list) {
				validate += it[ix];
			}
			if (validate == total) {
				System.out.println("result:" + list);
			} else {
				System.err.println("err:" + list);//输出这里就是算法不对
			}
			return;
		}
		int flag = 0;

		// 放入的角度
		if ((r - it[i] >= 0 && t[i - 1][r - it[i]] == true)) {
			flag++;
		}
		// 放入的角度->不放入的角度取反
		if ((r >= 0 && t[i - 1][r] == false)) {
			flag++;
		}
		// 情况分析：
		// 全部失败 走失败的
		// 一个失败一个成功 失败成功的都走
		// 全部成功 不走失败的
		// 即：存在成功的就走成功的 存在失败的就走失败的
		if (flag > 0) {// 1 or 2
			LinkedList<Integer> two = new LinkedList<Integer>();
			for (int j = 0; j < list.size(); j++) {
				two.add(list.get(j));
			}
			two.add(i);
			printAll(t, r - it[i], it, i - 1, level + 1, two, total);
		}
		if (flag < 2) {// 0 or 1
			printAll(t, r, it, i - 1, level + 1, list, total);// 存在匹配失败的
		}
	}

	// 放的角度判断
	private static void print1(boolean[][] t, int r, int[] it) {

		// 从最后一个物品往前
		for (int i = it.length - 1; i >= 1; i--) {
			// 减去当前价钱 去前一行找
			// 有就是有放入
			if (r - it[i] >= 0 && t[i - 1][r - it[i]] == true) {
				System.out.println("第" + i + "个物品,价钱" + it[i]);
				r = r - it[i];
			}
			// 如果t[i - 1][r]==true可以理解成是当前物品不放入 这里就不继续写了
		}
		// 最后一个物品的判断 it[0][0]=true
		if (r != 0) {
			System.out.println("第" + 0 + "个物品,价钱" + it[0]);
		}

	}

	// 不放的角度判断
	private static void print2(boolean[][] t, int r, int[] it) {
		for (int i = it.length - 1; i >= 1; i--) {
			// 减去当前价钱 去前一行找
			// 当前物品 有放入
			// t[i - 1][r]==true可以理解成是当前物品不放入 取反就是当前物品放入
			if (!(r >= 0 && t[i - 1][r] == true)) {
				System.out.println("第" + i + "个物品,价钱" + it[i]);
				r = r - it[i];
			}

		}

		if (r != 0) {
			System.out.println("第" + 0 + "个物品,价钱" + it[0]);
		}

	}

	// 不放的角度判断
	private static void print3(boolean[][] t, int r, int[] it) {
		for (int i = it.length - 1; i >= 1; i--) {
			// 减去当前价钱 去前一行找
			// 当前物品 有放入
			// t[i - 1][r]==true可以理解成是当前物品不放入 取反就是当前物品放入
			if ((r >= 0 && t[i - 1][r] == false)) {
				System.out.println("第" + i + "个物品,价钱" + it[i]);
				r = r - it[i];
			}

		}

		if (r != 0) {
			System.out.println("第" + 0 + "个物品,价钱" + it[0]);
		}

	}
}

硬币问题

有若干个不同额度的硬币，如需要一定的金额，最少需要几个硬币

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
package dynamic_programming;

public class DpCoins {
	public static void main(String[] args) {
		
		testCalCoins();

	}
	//测试
	private static void testCalCoins() {
		int[] c = { 1, 3, 5 };
		int m = (int) (1 + (Math.random() * 99));
		// m = 9;
		int r = calMinCoins(c, m);
		int r2 = calMinCoins2(c, m);

		System.out.println(m + "->" + r2 + ":" + r);
		if (r2 != r) {
			System.err.println("err");
			System.exit(0);
		}
	}

	// 算硬币
	private static int calMinCoins(int[] c, int m) {
		// 最少数量
		boolean[][] a = new boolean[m][m + 1];
		// 若干元 可以用若干个硬币达到
		// a[0][0] = true;// 啥都不放
		for (int x = 0; x < c.length; x++) {
			if (c[x] == m) {
				return 1;
			} else if (c[x] < m) {
				a[0][c[x]] = true;
			}
		}
		for (int i = 1; i < m; i++) {
			for (int j = 0; j <= m; j++) {
				if (a[i - 1][j]) {// 上一层如果放入
					a[i][j] = true;
					for (int x = 0; x < c.length; x++) {
						if (j + c[x] <= m) {
							a[i][j + c[x]] = true;
						}
					}

					// 核心
					if (a[i][m] == true) {
						return i + 1;
					}
				}
			}

		}
		System.err.println("错误1");
		System.exit(0);// exit
		return -1;// 算法错误的时候
	}

	// 算硬币
	private static int calMinCoins2(int[] c, int m) {
		// 最少数量
		boolean[] a = new boolean[m + 1];
		// 若干元 可以用若干个硬币达到
		for (int x = 0; x < c.length; x++) {
			if (c[x] == m) {
				return 1;
			} else if (c[x] < m) {
				a[c[x]] = true;
			}
		}
		for (int i = 1; i < m; i++) {
			for (int j = m; j >= 0; j--) {
				if (a[j]) {// 上一层如果放入
					for (int x = 0; x < c.length; x++) {
						if (j + c[x] <= m) {
							a[j + c[x]] = true;
						}
					}

					// 核心
					if (a[m] == true) {
						return i + 1;
					}
				}
			}

		}
		System.err.println("错误2");
		System.exit(0);// exit
		return -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
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
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
package dynamic_programming;

import java.util.Arrays;
import java.util.Random;

public class DpTestDistance {

	public static void main(String[] args) {
		// testLwst();
		 testLcs();
		String x = "efabeda";
		String y = "ecfafgbdc";
		int b = lcs(x, y);
		int a = lcs_(x.toCharArray(), y.toCharArray());
		//System.out.println(a + "," + b);
	}

	private static void testLcs() {
		int max = 1000;
		Random random = new Random();
		int l = 0;
		for (int i = 0; i < max; i++) {
			l = random.nextInt(9) + 1;
			String x = generateString(l);
			l = random.nextInt(9) + 1;
			String y = generateString(l);
			int a = lcs_(x.toCharArray(), y.toCharArray());
			int b = lcs(x, y);
			System.out.println(i + "->" + x + ":" + y);
			System.out.println(a + "," + b);
			if (a != b) {
				System.out.println("err");
				System.exit(0);
			}
		}
	}

	// 最长公共前缀
	public static int lcs(String a, String b) {
		return lcs(a.toCharArray(), b.toCharArray());
	}

	// 最长公共前缀
	public static int lcs(char[] a, char[] b) {

		int al = a.length;
		int bl = b.length;
		int[][] t = new int[al][bl];

		if (a[0] == b[0]) {// 首行首个
			t[0][0] = 1;// 相同不需要编辑
		} else {
			t[0][0] = 0;
		}
		// 首行
		for (int i = 1; i < bl; i++) {
			if (a[0] == b[i]) {
				// 当成前面的都不相等
				t[0][i] = 1;
			} else {
				// 当成前面的都不相等
				t[0][i] = t[0][i - 1];
			}

		}
		// 首列
		for (int i = 1; i < al; i++) {
			if (a[i] == b[0]) {
				// 当成前面的都不相等
				t[i][0] = 1;
			} else {
				// 当成前面的都不相等
				t[i][0] = t[i - 1][0];
				;
			}

		}
		for (int i = 1; i < al; i++) {
			for (int j = 1; j < bl; j++) {
				if (a[i] == b[j]) {
					t[i][j] = max(t[i - 1][j - 1] + 1, t[i][j - 1], t[i - 1][j]);
				} else {
					t[i][j] = max(t[i - 1][j - 1], t[i][j - 1], t[i - 1][j]);
				}
			}
		}

		return t[al - 1][bl - 1];
	}

	// 三个数字里的最大数
	private static int max(int x, int y, int z) {
		int m = x;
		if (y > m) {
			m = y;
		}
		if (z > m) {
			m = z;
		}
		return m;
	}

	private static void testLwst() {
		int max = 1000;
		Random random = new Random();
		int l = 0;
		for (int i = 0; i < max; i++) {
			l = random.nextInt(9) + 1;
			String x = generateString(l);
			l = random.nextInt(9) + 1;
			String y = generateString(l);
			int a = lwstDP(x.toCharArray(), y.toCharArray());
			int b = lwst(x, y);
			System.out.println(i + "->" + x + ":" + y);
			System.out.println(a + "-" + b);
			if (a != b) {
				System.err.println("err");
				System.exit(0);
			}
		}
	}

	// 来文斯坦距离 需要编辑的最短距离(删除 新增 修改)
	public static int lwst(String a, String b) {
		return lwst(a.toCharArray(), b.toCharArray());
	}

	// 来文斯坦距离 需要编辑的最短距离(删除 新增 修改)
	public static int lwst(char[] a, char[] b) {
		int al = a.length;
		int bl = b.length;
		int[][] t = new int[al][bl];
		if (a[0] == b[0]) {// 首行首个
			t[0][0] = 0;// 相同不需要编辑
		} else {
			t[0][0] = 1;
		}

		// 其实这里的x轴和y轴的首行都是根据规律计算的
		// 如ABAA和ABCD在计算的时候 可以添加这样一个辅助的 0来进行计算(这里的0不是代表字符‘0’代表绝对不匹配的字符)
		////////////////////
		// - 0 A B A A
		// 0 0 1 2 3 4
		// A 1 0 0 0 0
		// B 2 0 0 0 0
		// C 2 0 0 1 1
		// D 3 0 0 1 2
		//////////////////////////
		// 这里根据动态规划算法整理出来的的规律,
		// 则t[j][i]的值是通过t[j][i-1] 和t[j-1][i-1] 和t[j-1][i-1] 三个数里最小的那个进行推导出来的
		// 那么t[0][i] 是通过t[0][i-1] 和矩阵里该位置上方(值是i+2)、左上方的(值是i+1) 三个值进行比大小 取最小值
		// 也即是t[0][i-1]和i比哪个数更小
		// 那么求当i=1的时候 t[0][1]的数字的时候可以发现 就是去找 t[0][0]小还是 1小
		// 因为 t[0][0]的值可以是1也可能是0
		// 因此 要么 t[0][i-1] == i 要么 t[0][i-1] < i
		// 所以直接用 t[0][i-1]即可,
		// 因为使用的是动态规划解法的思想,后续判断(Y轴也是一样,就是换个角度)用相同的判断即可
		// 参考状态转移方程
		for (int i = 1; i < bl; i++) {
			if (a[0] == b[i]) {
				t[0][i] = i;// 当成前面的都不相等
			} else {
				// 去取所有的前面里最小的进行+1 在这里最小的就是 t[0][i-1]
				t[0][i] = t[0][i - 1] + 1;
			}

		}
		for (int i = 1; i < al; i++) {
			if (a[i] == b[0]) {
				t[i][0] = i;// 当成前面的都不相等
			} else {
				// 去取所有的前面里最小的进行+1 在这里最小的就是 t[i-1][0]
				t[i][0] = t[i - 1][0] + 1;
			}
		}
		for (int i = 1; i < al; i++) {
			for (int j = 1; j < bl; j++) {
				// 相等
				if (a[i] == b[j]) {
					// 去三个数字里找最小的
					t[i][j] = min(t[i - 1][j - 1], t[i][j - 1] + 1, t[i - 1][j] + 1);
				} else {
					// 去三个数里找最小的加一
					// 去三个数字里找最小的
					t[i][j] = min(t[i - 1][j - 1] + 1, t[i][j - 1] + 1, t[i - 1][j] + 1);
				}

			}
		}

		return t[al - 1][bl - 1];
	}

	// 三个数字里的最小数
	private static int min(int x, int y, int z) {
		int m = x;
		if (y < m) {
			m = y;
		}
		if (z < m) {
			m = z;
		}
		return m;
	}

	////////////////////////////////
	// 测试用-复制自极客时间
	////////////////////////////////////
	public static int lcs_(char[] a, char[] b) {
		int n = a.length;
		int m = b.length;
		int[][] maxlcs = new int[n][m];
		for (int j = 0; j < m; ++j) {// 初始化第 0 行：a[0..0] 与 b[0..j] 的 maxlcs
			if (a[0] == b[j])
				maxlcs[0][j] = 1;
			else if (j != 0)
				maxlcs[0][j] = maxlcs[0][j - 1];
			else
				maxlcs[0][j] = 0;
		}
		for (int i = 0; i < n; ++i) {// 初始化第 0 列：a[0..i] 与 b[0..0] 的 maxlcs
			if (a[i] == b[0])
				maxlcs[i][0] = 1;
			else if (i != 0)
				maxlcs[i][0] = maxlcs[i - 1][0];
			else
				maxlcs[i][0] = 0;
		}
		for (int i = 1; i < n; ++i) { // 填表
			for (int j = 1; j < m; ++j) {
				if (a[i] == b[j])
					maxlcs[i][j] = max_(maxlcs[i - 1][j], maxlcs[i][j - 1], maxlcs[i - 1][j - 1] + 1);
				else
					maxlcs[i][j] = max_(maxlcs[i - 1][j], maxlcs[i][j - 1], maxlcs[i - 1][j - 1]);
			}
		}

		return maxlcs[n - 1][m - 1];
	}

	private static int max_(int x, int y, int z) {
		int maxv = Integer.MIN_VALUE;
		if (x > maxv)
			maxv = x;
		if (y > maxv)
			maxv = y;
		if (z > maxv)
			maxv = z;
		return maxv;
	}

	public static int lwstDP(char[] a, char[] b) {
		int n = a.length;
		int m = b.length;
		int[][] minDist = new int[n][m];
		for (int j = 0; j < m; ++j) { // 初始化第 0 行:a[0..0] 与 b[0..j] 的编辑距离
			if (a[0] == b[j])
				minDist[0][j] = j;
			else if (j != 0)
				minDist[0][j] = minDist[0][j - 1] + 1;
			else
				minDist[0][j] = 1;
		}

		for (int i = 0; i < n; ++i) { // 初始化第 0 列:a[0..i] 与 b[0..0] 的编辑距离
			if (a[i] == b[0])
				minDist[i][0] = i;
			else if (i != 0)
				minDist[i][0] = minDist[i - 1][0] + 1;
			else
				minDist[i][0] = 1;
		}
		for (int i = 1; i < n; ++i) { // 按行填表
			for (int j = 1; j < m; ++j) {
				if (a[i] == b[j])
					minDist[i][j] = min_(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1, minDist[i - 1][j - 1]);
				else
					minDist[i][j] = min_(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1, minDist[i - 1][j - 1] + 1);
			}
		}
		return minDist[n - 1][m - 1];
	}

	private static int min_(int x, int y, int z) {
		int minv = Integer.MAX_VALUE;
		if (x < minv)
			minv = x;
		if (y < minv)
			minv = y;
		if (z < minv)
			minv = z;
		return minv;
	}

	private static final String CHARS = "abcdefg";//// 随机字符串池

	/**
	 * 随机字符串
	 * 
	 * @author lfy
	 * @param length
	 * @return
	 */
	public static String generateString(int length) {
		StringBuffer sb = new StringBuffer();
		Random random = new Random();
		for (int i = 0; i < length; i++) {
			sb.append(CHARS.charAt(random.nextInt(CHARS.length())));
		}
		return sb.toString();
	}

	public static void printArr(Object[][] arr) {
		System.out.println("----------------//");
		for (Object[] is : arr) {
			System.out.println(Arrays.toString(is));
		}

	}

	public static void printArr(Object[] arr) {
		System.out.println("-----------------/");
		System.out.println(Arrays.toString(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
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
package dynamic_programming;

public class DpTriangle {
	private static void testRandTri() {
		int[][] a = triangleRand(5);
		calMinDistance(a);

	}

	// 计算随机三角
	private static int calMinDistance(int[][] arr) {
		int l = arr.length;
		if (l == 0)
			return 0;
		if (l == 1)
			return arr[0][0];

		// 前2行都是固定的
		arr[0][0] = arr[0][0];
		arr[1][0] = arr[1][0] + arr[0][0];
		arr[1][1] = arr[1][1] + arr[0][0];
		for (int i = 2; i < l; i++) {
			// 首个和末尾只能由单个到达 直接累加
			arr[i][0] = arr[i - 1][0] + arr[i][0];
			arr[i][i] = arr[i - 1][i - 1] + arr[i][i];
			for (int j = 1; j < i; j++) {
				// 求的是最短路径 并且后续节点是固定的 所以求出到当前节点最短的路径即可
				// 判断能到达当前行的 哪一个更小
				if (arr[i - 1][j] > arr[i - 1][j - 1]) {
					arr[i][j] = arr[i - 1][j - 1] + arr[i][j];
				} else {
					arr[i][j] = arr[i - 1][j] + arr[i][j];
				}
			}
		}
		int idx = 0;
		for (int i = 1; i < l; i++) {
			if (arr[l - 1][i] < arr[l - 1][idx]) {
				idx = i;
			}
		}
		// print
		printDistance(arr, idx, l);
		return arr[l - 1][idx];
	}

	// 输出
	private static void printDistance(int[][] arr, int idx, int l) {
		System.out.println();
		System.out.println("最短:" + arr[l - 1][idx]);
		for (int i = l - 1; i > 0; i--) {
			if (idx == 0) {
				System.out.println(i + "行:" + idx + "个:" + (arr[i][idx] - arr[i - 1][idx]));

			} else if (idx == i || arr[i - 1][idx - 1] < arr[i - 1][idx]) {
				System.out.println(i + "行:" + idx + "个:" + (arr[i][idx] - arr[i - 1][--idx]));
				// --idx ;
			} else {
				System.out.println(i + "行:" + idx + "个:" + (arr[i][idx] - arr[i - 1][idx]));
			}

		}
		System.out.println(0 + "行:" + idx + "个:" + (arr[0][idx]));
	}

	// 随机三角
	private static int[][] triangleRand(int l) {
		int[][] a = new int[l][];
		for (int i = 0; i < l; i++) {
			a[i] = new int[i + 1];
			for (int j = 0; j < a[i].length; j++) {
				a[i][j] = (int) (Math.random() * 9 + 1);
			}
		}
		printTriangleRand(a, l);
		return a;
	}

	// 随机三角输出
	private static void printTriangleRand(int[][] a, int l) {
		// 比较规律的输出
		for (int i = 0; i < l - 1; i++) {
			int[] is = a[i];
			for (int n : is) {
				System.out.print("" + n + "  ");
			}
			System.out.println();
			for (int n : is) {
				System.out.print("↓↘");
			}
			System.out.println();
		}
		for (int n : a[l - 1]) {
			System.out.print("" + n + "  ");
		}

	}

	// 构建杨辉三角
	public static void triangle(int l) {
		int[][] a = new int[l][];
		for (int i = 0; i < l; i++) {
			a[i] = new int[i + 1];
			a[i][0] = 1;
			a[i][i] = 1;
			for (int j = 1; j < i; j++) {
				// 也算是动态规划吧。。
				a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
			}
		}
		printTriangle(a, l);
	}

	// 打印杨辉三角
	private static void printTriangle(int[][] a, int l) {
		int x = 1;// 空格
		int max = a[l - 1][l / 2];
		while (max / 10 > 0) {
			x++;
			max /= 10;
		}

		for (int i = 0; i < l; i++) {
			// 空格
			for (int j = i; j < l; j++) {
				for (int y = 0; y < x; y++) {
					System.out.print(" ");
				}
			}
			for (int j = 0; j < a[i].length; j++) {
				int z = 0;
				int c = a[i][j];
				while (c / 10 > 0) {
					z++;
					c /= 10;
				}
				z = x - z + 1;
				int hf = z / 2;
				for (int y = 0; y <= hf; y++) {
					System.out.print(" ");
				}
				System.out.print(a[i][j]);
				for (int y = hf; y < z; y++) {
					System.out.print(" ");
				}
			}
			System.out.println();
		}
	}
}

Review 英文文章

https://spring.io/guides

spring的引导介绍

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周继续学习该专栏中的40-42篇

内容为动态规划：简而言之，动态规划就是构建出最基础的东西，然后根据底层的数据再逐层构建出更上层的东西。直到计算玩全部的数据。并且动态规划的效率较高。

Share 分享

50条最经典的程序员至理名言
https://www.jianshu.com/p/8f446f967b2d