Dynamic-Programming
Fibonacci
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Fibonacci {
public static void main(String[] args) {
System.out.println(fibonacci(13));
}
public static int fibonacci(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
if (n < 2) {
return dp[n];
}
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
}
|
降维
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class Fibonacci {
public static void main(String[] args) {
System.out.println(fibonacci(13));
}
public static int fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int a = 0;
int b = 1;
for (int i = 2; i <= n; i++) {
int c = b + a;
a = b;
b = c;
}
return b;
}
}
|
最短路径 - Bellman-Ford
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
| public class BellmanFord {
static class Edge {
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
public static void main(String[] args) {
List<Edge> edges = List.of(
new Edge(6, 5, 9),
new Edge(4, 5, 6),
new Edge(1, 6, 14),
new Edge(3, 6, 2),
new Edge(3, 4, 11),
new Edge(2, 4, 15),
new Edge(1, 3, 9),
new Edge(1, 2, 7)
);
int[] dp = new int[7];
dp[1] = 0;
for (int i = 2; i < dp.length; i++) {
dp[i] = Integer.MAX_VALUE;
}
print(dp);
for (int i = 0; i < 5; i++) {
for (Edge e : edges) {
if(dp[e.from] != Integer.MAX_VALUE) {
dp[e.to] = Integer.min(dp[e.to], dp[e.from] + e.weight);
}
}
}
print(dp);
}
static void print(int[] dp) {
System.out.println(Arrays.stream(dp)
.mapToObj(i -> i == Integer.MAX_VALUE ? "∞" : String.valueOf(i))
.collect(Collectors.joining(",", "[", "]")));
}
}
|
不同路径-Leetcode 62
机器人要从左上角走到右下角，每次只能向右或向下，问一共有多少条不同路径？
分析，先考虑较为简单的情况
可能路径有三种情况：
分析：设坐标为，共有 m 行 n 列
1
2
3
| (0,0) (0,1)
(1,0) (1,1)
(2,0) (2,1)
|
如果终点是 (0,1) 那么只有一种走法
如果终点是 (1,0) 那么也只有一种走法
如果终点是 (1,1) 呢，它的走法是从它的上方走下来，或者从它的左边走过来，因此走法 = (0,1) + (1,0) = 2种
如果终点是 (2,0) 那么也只有一种走法
如果终点是 (2,1) 呢，它的走法是从它的上方走下来，或者从它的左边走过来，因此走法 = (1,1) + (2,0) = 3种
总结规律发现：
- 终点是 (0,1) (0,2) (0,3) … (0,n) 走法只有1种
- 终点是 (1,0) (2,0) (3,0) … (m,0) 走法也只有1种
- 除了上面两种情况以外，(i,j) 处的走法等于(i-1,j) + (i,j-1) 的走法之和，即为递推公式
画表格
1
2
3
| 0 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 6 10 15 21 28
|
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class UniquePaths {
public static void main(String[] args) {
int count = new UniquePaths().uniquePaths(3, 7);
System.out.println(count);
}
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
|
降维
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class UniquePaths {
public static void main(String[] args) {
int count = new UniquePaths().uniquePaths(3, 7);
System.out.println(count);
}
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
dp[0] = 1;
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
}
|
类似于不规则的杨辉三角
0-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
| public class KnapsackProblem {
static class Item {
int index;
String name;
int weight;
int value;
public Item(int index, String name, int weight, int value) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
@Override
public String toString() {
return "Item(" + name + ")";
}
}
public static void main(String[] args) {
Item[] items = new Item[]{
new Item(1, "黄金", 4, 1600),
new Item(2, "宝石", 8, 2400),
new Item(3, "白银", 5, 30),
new Item(4, "钻石", 1, 10_000),
};
System.out.println(select(items, 10));
}
static int select(Item[] items, int total) {
int[][] dp = new int[items.length][total + 1];
print(dp);
Item item0 = items[0];
for (int j = 0; j < total + 1; j++) {
if (j >= item0.weight) {
dp[0][j] = item0.value;
}
}
print(dp);
for (int i = 1; i < dp.length; i++) {
Item item = items[i];
for (int j = 1; j < total + 1; j++) {
int x = dp[i - 1][j];
if (j >= item.weight) {
int y = dp[i - 1][j - item.weight] + item.value;
dp[i][j] = Integer.max(x, y);
} else {
dp[i][j] = x;
}
}
print(dp);
}
return dp[dp.length - 1][total];
}
static void print(int[][] dp) {
System.out.println(" " + "-".repeat(63));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf(("%5d ".repeat(dp[0].length)) + "%n", array);
for (int[] d : dp) {
array = Arrays.stream(d).boxed().toArray();
System.out.printf(("%5d ".repeat(d.length)) + "%n", array);
}
}
}
|
降维
1
2
3
4
5
6
7
8
9
10
11
12
| static int select(Item[] items, int total) {
int[] dp = new int[total + 1];
for (Item item : items) {
for (int j = total; j > 0; j--) {
if (j >= item.weight) {
dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]);
}
}
System.out.println(Arrays.toString(dp));
}
return dp[total];
}
|
注意：内层循环需要倒序，否则 dp[j - item.weight] 的结果会被提前覆盖
完全背包问题
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
| public class KnapsackProblemComplete {
static class Item {
int index;
String name;
int weight;
int value;
public Item(int index, String name, int weight, int value) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
@Override
public String toString() {
return "Item(" + name + ")";
}
}
public static void main(String[] args) {
Item[] items = new Item[]{
new Item(1, "青铜", 2, 3),
new Item(2, "白银", 3, 4),
new Item(3, "黄金", 4, 7),
};
System.out.println(select(items, 6));
}
private static int select(Item[] items, int total) {
int[][] dp = new int[items.length][total + 1];
Item item0 = items[0];
for (int j = 0; j < total + 1; j++) {
if (j >= item0.weight) {
dp[0][j] = dp[0][j - item0.weight] + item0.value;
}
}
print(dp);
for (int i = 1; i < items.length; i++) {
Item item = items[i];
for (int j = 1; j < total + 1; j++) {
int x = dp[i - 1][j];
if (j >= item.weight) {
int y = dp[i][j - item.weight] + item.value;
dp[i][j] = Integer.max(x, y);
} else {
dp[i][j] = x;
}
}
print(dp);
}
return dp[dp.length - 1][total];
}
static void print(int[][] dp) {
System.out.println(" " + "-".repeat(63));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf(("%5d ".repeat(dp[0].length)) + "%n", array);
for (int[] d : dp) {
array = Arrays.stream(d).boxed().toArray();
System.out.printf(("%5d ".repeat(d.length)) + "%n", array);
}
}
}
|
降维
1
2
3
4
5
6
7
8
9
10
11
12
| private static int select(Item[] items, int total) {
int[] dp = new int[total + 1];
for (Item item : items) {
for (int j = 0; j < total + 1; j++) {
if (j >= item.weight) {
dp[j] = Integer.max(dp[j], dp[j - item.weight] + item.value);
}
}
System.out.println(Arrays.toString(dp));
}
return dp[total];
}
|
零钱兑换问题-Leetcode322
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
| public class ChangeMakingProblemLeetcode322 {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[][] dp = new int[coins.length][amount + 1];
for (int j = 1; j < amount + 1; j++) {
if (j >= coins[0]) {
dp[0][j] = 1 + dp[0][j - coins[0]];
} else {
dp[0][j] = max;
}
}
for (int i = 1; i < coins.length; i++) {
for (int j = 1; j < amount + 1; j++) {
if (j >= coins[i]) {
dp[i][j] = Math.min(dp[i - 1][j], 1 + dp[i][j - coins[i]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
print(dp);
}
int r = dp[coins.length - 1][amount];
return r > amount ? -1 : r;
}
public static void main(String[] args) {
ChangeMakingProblemLeetcode322 leetcode = new ChangeMakingProblemLeetcode322();
int count = leetcode.coinChange(new int[]{1, 2, 5}, 5);
System.out.println(count);
}
static void print(int[][] dp) {
System.out.println("-".repeat(18));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf(("%2d ".repeat(dp[0].length)) + "%n", array);
for (int[] d : dp) {
array = Arrays.stream(d).boxed().toArray();
System.out.printf(("%2d ".repeat(d.length)) + "%n", array);
}
}
}
|
降维
1
2
3
4
5
6
7
8
9
10
11
12
| public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j < amount + 1; j++) {
dp[j] = Math.min(dp[j], 1 + dp[j - coin]);
}
}
int r = dp[amount];
return r > amount ? -1 : r;
}
|
零钱兑换 II-Leetcode 518
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
| public class ChangeMakingProblemLeetcode518 {
public int change(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int j = coin; j < amount + 1; j++) {
dp[j] = dp[j] + dp[j - coin];
}
}
return dp[amount];
}
public static void main(String[] args) {
ChangeMakingProblemLeetcode518 leetcode = new ChangeMakingProblemLeetcode518();
int count = leetcode.change(new int[]{1, 2, 5}, 5);
System.out.println(count);
}
}
|
钢条切割问题
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
| public class CutRodProblem {
static int cut(int[] values, int n) {
int[][] dp = new int[values.length][n + 1];
for (int i = 1; i < values.length; i++) {
int v = values[i];
for (int j = 1; j < n + 1; j++) {
if (j >= i) {
dp[i][j] = Integer.max(dp[i - 1][j], v + dp[i][j - i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
print(dp);
}
return dp[values.length - 1][n];
}
public static void main(String[] args) {
System.out.println(cut(new int[]{0, 1, 5, 8, 9}, 4));
}
}
|
降维
1
2
3
4
5
6
7
8
9
10
11
| static int cut(int[] values, int n) {
int[] dp = new int[n + 1];
for (int i = 1; i < values.length; i++) {
int v = values[i];
for (int j = i; j < n + 1; j++) {
dp[j] = Integer.max(dp[j], v + dp[j - i]);
}
System.out.println(Arrays.toString(dp));
}
return dp[n];
}
|
本质上是完全背包问题，把钢条总长度看作背包容量，切分后的钢条看作物品。只是
类似题目 Leetcode-343 整数拆分
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
| public class Leetcode343 {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, 1);
dp[0] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n + 1; j++) {
if (j >= i) {
dp[j] = Integer.max(dp[j], i * dp[j - i]);
}
}
System.out.println(Arrays.toString(dp));
}
return dp[n];
}
public int integerBreak2(int n) {
int[][] dp = new int[n][n + 1];
Arrays.fill(dp[0], 1);
for (int i = 1; i < n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n + 1; j++) {
if (j >= i) {
dp[i][j] = Integer.max(dp[i - 1][j], i * dp[i][j - i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
print(dp);
}
return dp[n - 1][n];
}
public static void main(String[] args) {
Leetcode343 code = new Leetcode343();
System.out.println(code.integerBreak(4));
System.out.println(code.integerBreak(10));
}
}
|
最长公共子串
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
| public class LCSubstring {
static int lcs(String a, String b) {
int[][] dp = new int[b.length()][a.length()];
int max = 0;
for (int i = 0; i < b.length(); i++) {
for (int j = 0; j < a.length(); j++) {
if (a.charAt(j) == b.charAt(i)) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
max = Integer.max(dp[i][j], max);
} else {
dp[i][j] = 0;
}
}
}
print(dp, a, b);
return max;
}
static void print(int[][] dp, String a, String b) {
System.out.println("-".repeat(23));
Object[] array = a.chars().mapToObj(i -> String.valueOf((char) i)).toArray();
System.out.printf(" "+"%2s ".repeat(a.length()) + "%n", array);
for (int i = 0; i < b.length(); i++) {
int[] d = dp[i];
array = Arrays.stream(d).boxed().toArray();
System.out.printf(b.charAt(i) + " " + "%2d ".repeat(d.length) + "%n", array);
}
}
public static void main(String[] args) {
System.out.println(lcs("itheima", "then"));
}
}
|
类似题目 Leetcode-718 最长重复子数组
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
| public class Leetcode718 {
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length + 1;
int n = nums2.length + 1;
int[] dp = new int[n];
int max = 0;
for (int i = 1; i < m; i++) {
for (int j = n - 1; j > 0; j--) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[j] = dp[j - 1] + 1;
max = Integer.max(max, dp[j]);
} else {
dp[j] = 0;
}
}
}
return max;
}
public int findLength1(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] dp = new int[n];
int max = 0;
for (int i = 0; i < m; i++) {
for (int j = n - 1; j >= 0; j--) {
if (nums1[i] == nums2[j]) {
if (i == 0 || j == 0) {
dp[j] = 1;
} else {
dp[j] = dp[j - 1] + 1;
}
max = Integer.max(max, dp[j]);
} else {
dp[j] = 0;
}
}
}
return max;
}
public int findLength2(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length][nums2.length];
int max = 0;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j]) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
max = Integer.max(max, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return max;
}
public static void main(String[] args) {
Leetcode718 code = new Leetcode718();
System.out.println(code.findLength(new int[]{1, 2, 3, 2, 1}, new int[]{3, 2, 1, 4, 7}));
System.out.println(code.findLength(new int[]{1, 0, 0, 0, 1}, new int[]{1, 0, 0, 1, 1}));
}
}
|
最长公共子序列
最长公共子序列-Leetcode 1143
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
| public class LCSubsequence {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; i++) {
char a = text1.charAt(i - 1);
for (int j = 1; j < n + 1; j++) {
char b = text2.charAt(j - 1);
if (a == b) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
print(dp, text2, text1);
return dp[m][n];
}
static void print(int[][] dp, String a, String b) {
System.out.println("-".repeat(23));
Object[] array = a.chars().mapToObj(i -> String.valueOf((char) i)).toArray();
System.out.printf(" " + "%2s ".repeat(a.length()) + "%n", array);
for (int i = 0; i < b.length(); i++) {
int[] d = dp[i + 1];
array = Arrays.stream(d).boxed().toArray();
System.out.printf(b.charAt(i) + " " + "%2d ".repeat(d.length) + "%n", array);
}
}
public static void main(String[] args) {
LCSubsequence code = new LCSubsequence();
System.out.println(code.longestCommonSubsequence("abcde", "ace"));
System.out.println(code.longestCommonSubsequence("ba", "yby"));
}
}
|
两个字符串的删除操作-Leetcode 583
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
| public class Leetcode538 {
public static void main(String[] args) {
Leetcode538 code = new Leetcode538();
System.out.println(code.minDistance("leetcode", "etco"));
System.out.println(code.minDistance("eat", "sea"));
System.out.println(code.minDistance("park", "spake"));
}
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
char[] chars1 = word1.toCharArray();
char[] chars2 = word2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; i++) {
int x = chars1[i - 1];
for (int j = 1; j < n + 1; j++) {
int y = chars2[j - 1];
if (x == y) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return m + n - dp[m][n] - dp[m][n];
}
}
|
最长上升子序列-Leetcode 300
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
| public class Leetcode300 {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Integer.max(dp[i], dp[j] + 1);
}
}
System.out.println(Arrays.toString(dp));
}
return Arrays.stream(dp).max().getAsInt();
}
public static void main(String[] args) {
Leetcode300 code = new Leetcode300();
System.out.println(code.lengthOfLIS(new int[]{1, 3, 6, 4, 9}));
}
}
|
Catalan 数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public class Catalan {
public static void main(String[] args) {
System.out.println(catalan(6));
}
static int catalan(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n + 1; i++) {
for (int j = 0; j < i; j++) {
System.out.print("(" + j + " " + (i - 1 - j) + ")\t");
dp[i] += dp[j] * dp[i - 1 - j];
}
System.out.println();
System.out.println(Arrays.toString(dp));
}
return dp[n];
}
}
|
Leetcode-96 不同的二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int j = 2; j < n + 1; j++) {
for (int i = 0; i < j; i++) {
dp[j] += dp[i] * dp[j - 1 - i];
}
}
return dp[n];
}
}
|
Leetcode-22 括号生成
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
| public class Leetcode22 {
public List<String> generateParenthesis(int n) {
ArrayList<String>[] dp = new ArrayList[n + 1];
dp[0] = new ArrayList<>(List.of(""));
dp[1] = new ArrayList<>(List.of("()"));
for (int j = 2; j < n + 1; j++) {
dp[j] = new ArrayList<>();
for (int i = 0; i < j; i++) {
System.out.printf("(%d,%d)\t", i, j - 1 - i);
for (String k1 : dp[i]) {
for (String k2 : dp[j - 1 - i]) {
dp[j].add("(" + k1 + ")" + k2);
}
}
}
System.out.println(dp[j]);
}
return dp[n];
}
public static void main(String[] args) {
Leetcode22 code = new Leetcode22();
System.out.println(code.generateParenthesis(4));
}
}
|
买票找零问题
售票处售卖球票，每张票 50 元。有2n人前来买票
- 其中一半人手持 50 元钞票
- 另一半人手持 100 元钞票
若售票处开始没有任何零钱，问：有多少种排队方式，能够让售票顺畅进行。
思路：
- 把手持 50 元钞票的人视为左括号
- 把手持 100 元钞票的人视为右括号
- 左右括号合法配对，即先出现左括号，再出现右括号，就可以让售票顺畅执行
可以看到，问题又变成了求解 n 的卡特兰数
其它问题
| 题号 |
标题 |
| Leetcode 331 |
验证二叉树的前序序列化 |
| Leetcode 894 |
所有可能的满二叉树 |
|
|
打家劫舍-Leetcode 198
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
| public class HouseRobberLeetcode198 {
public int rob(int[] nums) {
int len = nums.length;
if (len == 1) {
return nums[0];
}
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Integer.max(nums[0], nums[1]);
for (int i = 2; i < len; i++) {
dp[i] = Integer.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[len - 1];
}
public static void main(String[] args) {
HouseRobberLeetcode198 code = new HouseRobberLeetcode198();
System.out.println(code.rob(new int[]{2, 7, 9, 3, 1}));
System.out.println(code.rob(new int[]{2, 1, 1, 2}));
}
}
|
Travelling salesman problem
旅行商问题
java 代码
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
| public class TravellingSalesmanProblem {
public static void main(String[] args) {
int[][] graph = {
{0, 1, 2, 3},
{1, 0, 6, 4},
{2, 6, 0, 5},
{3, 4, 5, 0},
};
System.out.println(6 >> (0-1));
}
static int tsp1(int[][] graph) {
int n = graph.length;
int[][] dp = new int[1 << n][n];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE / 2);
}
dp[1][0] = 0;
for (int mask = 1; mask < 1 << n; mask++) {
for (int i = 0; i < n; i++) {
if ((mask & 1 << i) == 0) continue;
for (int j = 0; j < n; j++) {
if ((mask & 1 << j) != 0) continue;
dp[mask | 1 << j][j] = Math.min(dp[mask | 1 << j][j], dp[mask][i] + graph[i][j]);
}
}
print(dp);
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
res = Math.min(res, dp[(1 << n) - 1][i] + graph[i][0]);
}
return res;
}
static boolean contains(int set, int city) {
return (set >> (city - 1) & 1) == 1;
}
static int exclude(int set, int city) {
return set ^ (1 << (city - 1));
}
static int tsp(int[][] g) {
int n = g.length;
int m = 1 << (n - 1);
int[][] dp = new int[n][m];
for (int i = 0; i < n; i++) {
dp[i][0] = g[i][0];
}
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
dp[i][j] = Integer.MAX_VALUE / 2;
if (contains(j, i)) continue;
for (int k = 1; k < n; k++) {
if (contains(j, k)) {
dp[i][j] = Math.min(dp[i][j], g[i][k] + dp[k][exclude(j, k)]);
}
}
}
print(dp);
}
return dp[0][m - 1];
}
static void print(int[][] dist) {
System.out.println("-------------------------");
for (int[] row : dist) {
System.out.println(Arrays.stream(row).boxed()
.map(x -> x >= Integer.MAX_VALUE / 2 ? "∞" : String.valueOf(x))
.map(s -> String.format("%2s", s))
.collect(Collectors.joining(",", "[", "]")));
}
}
}
|
其它题目
| 题号 |
标题 |
| 无 |
集合覆盖问题 |
| 无 |
扔鸡蛋问题 |
| Leetcode 72 |
编辑距离 |
| Leetcode 121 |
买股票的最佳时机 |
组合总和 IV-Leetcode 377
不要被题目名字误导了，本题类似于零钱兑换518题，区别在于零钱兑换求的是组合数，本题求的是排列数
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
| public class CombinationLeetcode377 {
static int combinationSum4(int[] nums, int target) {
return change(nums, target);
}
static int change(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int j = 1; j < amount + 1; j++) {
for (int coin : coins) {
if (j >= coin) {
dp[j] += dp[j - coin];
}
}
System.out.println(Arrays.toString(dp));
}
return dp[amount];
}
public static void main(String[] args) {
System.out.println(combinationSum4(new int[]{1, 2, 3}, 4));
}
}
|
