动态规划
动态规划是计算机中解决最优化的问题的一种方法。
找出最长的递增的子序列
给你一个无序的数组 nums = [1,5,2,4,3]，要求找出其中最长的递增的子序列。比如1,2,4 或者1,2,3，我们要求这个算法只返回最长序列的长度。也就是3。
暴力枚举/暴力搜索
从1出发，当前最长序列的长度是3
最后我们还要从5,2,4...出发去算长度。
java
public class Search {
public static void main(String[] args) {
int[] nums = {1,5,2,4,3};
System.out.println(lengthOfArray(nums));
}
static int length(int[] nums, int i){
int maxLen = 1;
if (i == nums.length-1) {
return maxLen;
}
// 从第i 个往后找 大于第j 个树就是自增序列
for (int j = i; j < nums.length ; j++) {
if (nums[j]> nums[i]) {
maxLen = Math.max(maxLen,length(nums, j)+1);
}
}
return maxLen;
}
static int lengthOfArray(int[] nums){
int maxLen = 0;
for (int i = 0; i <nums.length ; i++) {
maxLen = Math.max(maxLen, length(nums,i));
}
return maxLen;
}
}
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
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
记忆化搜索/剪枝
java
public class Search {
public static void main(String[] args) {
int[] nums = {1,5,2,4,3};
System.out.println(lengthOfArray(nums));
}
// 剪枝
static Map<Integer, Integer> brunch = new HashMap<>();
static int length(int[] nums, int i){
if (brunch.containsKey(i)) {
return brunch.get(i);
}
int maxLen = 1;
if (i == nums.length-1) {
return maxLen;
}
// 从第i 个往后找 大于第j 个树就是自增序列
for (int j = i; j < nums.length ; j++) {
if (nums[j]> nums[i]) {
maxLen = Math.max(maxLen,length(nums, j)+1);
}
}
brunch.put(i, maxLen);
return maxLen;
}
static int lengthOfArray(int[] nums){
int maxLen = 0;
for (int i = 0; i <nums.length ; i++) {
maxLen = Math.max(maxLen, length(nums,i));
}
return maxLen;
}
}
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
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
避免重复的计算，将结果缓存起来，来加速整个计算的过程。bi
最长回文子串
- 什么是回文串: 形如
abccba这种正着读，倒着读完全一样的字符串就是回文串。
背包问题
题目：现在有4个物品，背包总容量是8，背包最多能装入多少价值的物品？
| 物品 | 体积 | 价值 |
|---|---|---|
| 物品1 | 2 | 3 |
| 物品2 | 3 | 4 |
| 物品3 | 4 | 5 |
| 物品4 | 5 | 6 |