# 动态规划、回溯、贪心，分治

2020/03/16 23:43

• 从斐波那契数列开始

public class Fibonacci {
private static int num = 0;
private Fibonacci() {
}
public static int fib(int n) {
num++;
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}

public static void main(String[] args) {
num = 0;
int n = 20;
long start = System.nanoTime();
int res = Fibonacci.fib(n);
long end = System.nanoTime();
System.out.println(res);
System.out.println((end - start) / 1000000000.0);
System.out.println(num);
}
}

6765
3.96599E-4
21891

102334155
0.473162902
331160281

267914296
1.302307318
866988873

public class Fibonacci {
private static int num = 0;
private static List<Integer> memo = new ArrayList<>();
private Fibonacci() {
}
//记忆化搜索
public static int fib(int n) {
num++;
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (memo.get(n) == -1) {
memo.set(n,fib(n - 1) + fib(n - 2));
}
return memo.get(n);
}

public static void main(String[] args) {
num = 0;
int n = 42;
for (int i = 0;i <= n;i++) {
}
long start = System.nanoTime();
int res = Fibonacci.fib(n);
long end = System.nanoTime();
System.out.println(res);
System.out.println((end - start) / 1000000000.0);
System.out.println(num);
}
}

267914296
4.2859E-5
83

public class Fibonacci {
private static List<Integer> memo = new ArrayList<>();
private Fibonacci() {
}
//动态规划
public static int fib(int n) {
for (int i = 2;i <= n;i++) {
memo.add(memo.get(i - 1) + memo.get(i - 2));
}
return memo.get(n);
}

public static void main(String[] args) {
int n = 42;
long start = System.nanoTime();
int res = Fibonacci.fib(n);
long end = System.nanoTime();
System.out.println(res);
System.out.println((end - start) / 1000000000.0);
}
}

267914296
4.456E-5

• 背包问题

F(n,C)考虑将n个物品放进容量为C的背包，使得价值最大。

F(i,c) = F(i - 1,c)                            不考虑新来的 i 放进背包，则只剩下i - 1个物品

= v(i) + F(i - 1,c - w(i))        考虑新来的 i 放进背包

F(i,c) = max(F(i - 1,c) ,v(i) + F(i - 1,c - w(i)))

public class Knapsack {
private int[][] memo;
public int knapsack(int[] w,int[] v,int C) {
int n = w.length;
memo = new int[n][C + 1];
for (int i = 0;i < n;i++) {
for (int j = 0;j <= C;j++) {
memo[i][j] = -1;
}
}
return bestValue(w,v,n - 1,C);
}

/**
* 用[0..index]的物品，填充容积为c的背包的最大价值
* @param w
* @param v
* @param index
* @param c
* @return
*/
private int bestValue(int[] w,int[] v,int index,int c) {
if (index < 0 || c <= 0) {
return 0;
}
if (memo[index][c] != -1) {
return memo[index][c];
}
int res = bestValue(w,v,index - 1,c);
if (c >= w[index]) {
res = Math.max(res,v[index] + bestValue(w,v,index - 1,c - w[index]));
}
memo[index][c] = res;
return res;
}
}

public class Knapsack {
private int[][] memo;
public int knapsack(int[] w,int[] v,int C) {
if (w.length != v.length) {
throw new IllegalArgumentException("重量数组与价值数组长度必须相等");
}
int n = w.length;
if (n == 0) {
return 0;
}
int[][] memo = new int[n][C + 1];
for (int i = 0;i < n;i++) {
for (int j = 0;j <= C;j++) {
memo[i][j] = -1;
}
}
for (int j = 0;j <= C;j++) {
memo[0][j] = j >= w[0] ? v[0] : 0;
}
for (int i = 1;i < n;i++) {
for (int j = 0;j <= C;j++) {
memo[i][j] = memo[i - 1][j];
if (j >= w[i]) {
memo[i][j] = Math.max(memo[i][j],v[i] + memo[i - 1][j - w[i]]);
}
}
}
return memo[n - 1][C];
}
}

LeetCode算法题 中的第17题的代码中，我们来加入一些输出信息

class Solution {
private final List<String> letterMap = Arrays.asList(" ","","abc","def",
"ghi","jkl","mno","pqrs","tuv","wxyz");
private List<String> res = new ArrayList<>();

public List<String> letterCombinations(String digits) {
findCombination(digits,0,"");
if (res.contains("")) {
res.remove("");
}
return res;
}

/**
* s中保存了此时从digits[0..index-1]翻译得到的一个字母字符串
* 寻找和digits[index]匹配的字母，获得digits[0..index]翻译得到的解
* @param digits
* @param index
* @param s
*/
private void findCombination(String digits,int index,String s) {
System.out.println(index + " : " + s);
if (index == digits.length()) {
System.out.println("获得 " + s + ", return");
return;
}
Character c = digits.charAt(index);
if (c < '0' || c > '9' || c == '1') {
throw new IllegalArgumentException("字符不符合要求");
}
String letters = letterMap.get(c - '0');
for (int i = 0;i < letters.length();i++) {
System.out.println("digits[" + index + "] = " + c +", 使用了 " + letters.substring(i,i + 1));
findCombination(digits,index + 1,s + letters.substring(i,i + 1));
}
System.out.println("digits[" + index + "] = " + c + " 完成，return");
}

public static void main(String[] args) {
List<String> res = new Solution().letterCombinations("234");
res.stream().forEach(System.out::println);
}
}

0 :
digits[0] = 2, 使用了 a
1 : a
digits[1] = 3, 使用了 d
digits[2] = 4, 使用了 g

digits[2] = 4, 使用了 h

digits[2] = 4, 使用了 i

digits[2] = 4 完成，return
digits[1] = 3, 使用了 e
2 : ae
digits[2] = 4, 使用了 g
3 : aeg

digits[2] = 4, 使用了 h
3 : aeh

digits[2] = 4, 使用了 i
3 : aei

digits[2] = 4 完成，return
digits[1] = 3, 使用了 f
2 : af
digits[2] = 4, 使用了 g
3 : afg

digits[2] = 4, 使用了 h
3 : afh

digits[2] = 4, 使用了 i
3 : afi

digits[2] = 4 完成，return
digits[1] = 3 完成，return
digits[0] = 2, 使用了 b
1 : b
digits[1] = 3, 使用了 d
2 : bd
digits[2] = 4, 使用了 g
3 : bdg

digits[2] = 4, 使用了 h
3 : bdh

digits[2] = 4, 使用了 i
3 : bdi

digits[2] = 4 完成，return
digits[1] = 3, 使用了 e
2 : be
digits[2] = 4, 使用了 g
3 : beg

digits[2] = 4, 使用了 h
3 : beh

digits[2] = 4, 使用了 i
3 : bei

digits[2] = 4 完成，return
digits[1] = 3, 使用了 f
2 : bf
digits[2] = 4, 使用了 g
3 : bfg

digits[2] = 4, 使用了 h
3 : bfh

digits[2] = 4, 使用了 i
3 : bfi

digits[2] = 4 完成，return
digits[1] = 3 完成，return
digits[0] = 2, 使用了 c
1 : c
digits[1] = 3, 使用了 d
2 : cd
digits[2] = 4, 使用了 g
3 : cdg

digits[2] = 4, 使用了 h
3 : cdh

digits[2] = 4, 使用了 i
3 : cdi

digits[2] = 4 完成，return
digits[1] = 3, 使用了 e
2 : ce
digits[2] = 4, 使用了 g
3 : ceg

digits[2] = 4, 使用了 h
3 : ceh

digits[2] = 4, 使用了 i
3 : cei

digits[2] = 4 完成，return
digits[1] = 3, 使用了 f
2 : cf
digits[2] = 4, 使用了 g
3 : cfg

digits[2] = 4, 使用了 h
3 : cfh

digits[2] = 4, 使用了 i
3 : cfi

digits[2] = 4 完成，return
digits[1] = 3 完成，return
digits[0] = 2 完成，return
aeg
aeh
aei
afg
afh
afi
bdg
bdh
bdi
beg
beh
bei
bfg
bfh
bfi
cdg
cdh
cdi
ceg
ceh
cei
cfg
cfh
cfi

findCombination(digits,0,"");

0 :

findCombination(digits,index + 1,s + letters.substring(i,i + 1));

findCombination(digits,1,"a");

1 : a

findCombination(digits,2,"ad");

findCombination(digits,3,"adg");

findCombination(digits,3,"adh");

findCombination(digits,3,"adi");

for (int i = 0;i < letters.length();i++) {
System.out.println("digits[" + index + "] = " + c +", 使用了 " + letters.substring(i,i + 1));
findCombination(digits,index + 1,s + letters.substring(i,i + 1));
}

letters的ghi都被遍历过了，整个for循环结束，打印

digits[2] = 4 完成，return

findCombination(digits,2,"ae");

2 : ae

findCombination(digits,3,"aeg");

1. 完全平方数：1,4,9,16......
2. 12 = 4 + 4 + 4
3. 13 = 4 + 9

class Solution {
@SuppressWarnings("unchecked")
public int eraseOverlapIntervals(List<Interval> intervals) {
int n = intervals.size();
if (n == 0) {
return 0;
}
Collections.sort(intervals);
//memo[i]表示使用intervals[0...i]的区间能构成的最长不重叠区间序列
List<Integer> memo = new ArrayList<>(n);
//设置所有不重叠区间的长度为1，表示都不重叠
for (int i = 0;i < n;i++) {
}
for (int i = 1;i < n;i++) {
//求memo[i]
for (int j = 0;j < i;j++) {
//如果条件成立，就说明第i个区间可以跟在第j个区间的后面
if (intervals.get(i).getStart() >= intervals.get(j).getEnd()) {
memo.set(i,Math.max(memo.get(i),1 + memo.get(j)));
}
}
}
//取出memo中的最大值
int res = memo.stream().max(Comparator.comparing(i -> i)).orElse(1);
return n - res;
}

public static void main(String[] args) {
List<Interval> intervals = Arrays.asList(
new Interval(1,2),
new Interval(1,2),
new Interval(1,2),
new Interval(1,3));
Solution solution = new Solution();
System.out.println(solution.eraseOverlapIntervals(intervals));
}
}

@AllArgsConstructor
@Data
class Interval implements Comparable {
private int start;
private int end;
public Interval() {
this.start = 0;
this.end = 0;
}

@Override
public int compareTo(Object o) {
Interval o1 = (Interval) o;
if (this.start != o1.start) {
return this.start - o1.start;
}else {
return this.end - o1.end;
}
}
}

1. 每次选择中，每个区间的结尾很重要。
2. 结尾越小，留给了后面越大的空间，后面越有可能容纳更多区间。

class Solution {
@SuppressWarnings("unchecked")
public int eraseOverlapIntervals(List<Interval> intervals) {
int n = intervals.size();
if (n == 0) {
return 0;
}
Collections.sort(intervals);
int res = 1;
int pre = 0;
for (int i = 1;i < n;i++) {
if (intervals.get(i).getStart() >= intervals.get(pre).getEnd()) {
res++;
pre = i;
}
}
return n - res;
}

public static void main(String[] args) {
List<Interval> intervals = Arrays.asList(
new Interval(1,2),
new Interval(1,2),
new Interval(1,2),
new Interval(1,3));
Solution solution = new Solution();
System.out.println(solution.eraseOverlapIntervals(intervals));
}
}

@AllArgsConstructor
@Data
class Interval implements Comparable {
private int start;
private int end;
public Interval() {
this.start = 0;
this.end = 0;
}

@Override
public int compareTo(Object o) {
Interval o1 = (Interval) o;
if (this.end != o1.end) {
return this.end - o1.end;
}else {
return this.start - o1.start;
}
}
}

0
0 收藏

0 评论
0 收藏
0