动态规划、回溯、贪心,分治

原创
2020/03/16 23:43
阅读数 1.8K

动态规划篇

  • 从斐波那契数列开始

我们先给出斐波那契数列的常用算法类

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

此时我们调大n的值为40

运行结果

102334155
0.473162902
331160281

再调大n的值为42

267914296
1.302307318
866988873

我们可以看到此处随着n的增大,时间是几何倍数增长,由此我们可知斐波那契数列的时间复杂度为O(2^n)

但我们发现斐波那契数列的存在着大量的重复计算,如下图所示,我们来看计算一个n=5的时候都有哪些重复计算的地方

在这里我们可以看到3被计算了2次。

而2则被计算了3次,这还是n = 5的情况下,如果随着n值的增大,重复计算的次数就会越来越多。

所以我们给出了一个新的记录重复计算值不需要重新计算的斐波那契算法类

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++) {
            memo.add(-1);
        }
        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);
    }
}

这次我们再来计算n = 42,运行结果

267914296
4.2859E-5
83

由结果可知,当我们减少了计算次数,斐波那契算法的时间复杂度从O(2^n)一下子降到了O(n)级别,这就相当于我们在列表中命中了缓存,无需866988873次计算,而计算次数只降低到了83次。

很明显递归的求解是一种自上而下的思考方式,那我们可不可以换一种思考的方式,使用自下而上的方式来求解呢

public class Fibonacci {
    private static List<Integer> memo = new ArrayList<>();
    private Fibonacci() {
    }
    //动态规划
    public static int fib(int n) {
        memo.add(0);
        memo.add(1);
        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

而这样的一种自下而上的计算方式,我们就称之为动态规划。将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。总体的思路如下图

  • 背包问题

有一个背包,它的容量为C。现在有n种不同的物品,编号为0..n-1,其中每一件物品的重量为w(i),价值为v(i)。问可以向这个背包中盛放哪些物品,使得在不超过背包容量的基础上,物品的总价值最大。

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

状态转移方程

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

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

根据以上两种状态,我们要选出这两种状态的最大值max

最终方程式

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()) {
            res.add(s);
            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
2 : ad
digits[2] = 4, 使用了 g
3 : adg
获得 adg, return
digits[2] = 4, 使用了 h
3 : adh
获得 adh, return
digits[2] = 4, 使用了 i
3 : adi
获得 adi, return
digits[2] = 4 完成,return
digits[1] = 3, 使用了 e
2 : ae
digits[2] = 4, 使用了 g
3 : aeg
获得 aeg, return
digits[2] = 4, 使用了 h
3 : aeh
获得 aeh, return
digits[2] = 4, 使用了 i
3 : aei
获得 aei, return
digits[2] = 4 完成,return
digits[1] = 3, 使用了 f
2 : af
digits[2] = 4, 使用了 g
3 : afg
获得 afg, return
digits[2] = 4, 使用了 h
3 : afh
获得 afh, return
digits[2] = 4, 使用了 i
3 : afi
获得 afi, return
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
获得 bdg, return
digits[2] = 4, 使用了 h
3 : bdh
获得 bdh, return
digits[2] = 4, 使用了 i
3 : bdi
获得 bdi, return
digits[2] = 4 完成,return
digits[1] = 3, 使用了 e
2 : be
digits[2] = 4, 使用了 g
3 : beg
获得 beg, return
digits[2] = 4, 使用了 h
3 : beh
获得 beh, return
digits[2] = 4, 使用了 i
3 : bei
获得 bei, return
digits[2] = 4 完成,return
digits[1] = 3, 使用了 f
2 : bf
digits[2] = 4, 使用了 g
3 : bfg
获得 bfg, return
digits[2] = 4, 使用了 h
3 : bfh
获得 bfh, return
digits[2] = 4, 使用了 i
3 : bfi
获得 bfi, return
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
获得 cdg, return
digits[2] = 4, 使用了 h
3 : cdh
获得 cdh, return
digits[2] = 4, 使用了 i
3 : cdi
获得 cdi, return
digits[2] = 4 完成,return
digits[1] = 3, 使用了 e
2 : ce
digits[2] = 4, 使用了 g
3 : ceg
获得 ceg, return
digits[2] = 4, 使用了 h
3 : ceh
获得 ceh, return
digits[2] = 4, 使用了 i
3 : cei
获得 cei, return
digits[2] = 4 完成,return
digits[1] = 3, 使用了 f
2 : cf
digits[2] = 4, 使用了 g
3 : cfg
获得 cfg, return
digits[2] = 4, 使用了 h
3 : cfh
获得 cfh, return
digits[2] = 4, 使用了 i
3 : cfi
获得 cfi, return
digits[2] = 4 完成,return
digits[1] = 3 完成,return
digits[0] = 2 完成,return
adg
adh
adi
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,""进入了,所以首次打印的是

0 :

然后我们要从digits[0]开始处理,由于digits[0]等于‘2’,而'2'在letterMap中代表了"abc",我们首先使用了"abc"的第一个"a",就进入了第一次递归调用

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

此时我们的index就变成了1,s就变成了"a"。相当于调用的是

findCombination(digits,1,"a");

所以此时打印了

1 : a

然后我们要从digtis[1]进行处理,digits[1]等于'3','3'在letterMap中代表了"def",我们使用了"def"的第一个"d",就进入了第二次递归调用

findCombination(digits,2,"ad");

所以此时打印了

2 : ad

然后我们要从digtis[2]进行处理,digits[2]等于'4','4'在letterMap中代表了"ghi",我们使用了"ghi"的第一个"g",就进入了第三次递归调用

findCombination(digits,3,"adg");

所以此时打印了

3 : adg

当index等于3的时候,它等于digits字符串的长度,说明我们已经找到了一个合法的字符串,我们打印输出了

获得 adg, return

注意,这里return回去以后,返回到的是index等于2的时候,digits[2]等于'4','4'在letterMap中代表了"ghi",我们使用了"ghi"的第二个"h",就进入了第四次递归调用

findCombination(digits,3,"adh");

当index等于3的时候,它等于digits字符串的长度,说明我们已经找到了一个合法的字符串,我们打印输出了

获得 adh, return

这里return回去以后,返回到的index依然是2,digits[2]等于'4','4'在letterMap中代表了"ghi",我们使用了"ghi"的第三个"i",就进入了第五次递归调用

findCombination(digits,3,"adi");

当index等于3的时候,它等于digits字符串的长度,说明我们已经找到了一个合法的字符串,我们打印输出了

获得 adi, return

这里return回去以后,返回到的index依然是2,digits[2]等于'4','4'在letterMap中代表了"ghi"。但由于

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

这里return回去以后,返回到的index为1,digits[1]等于'3','3'在letterMap中代表了"def",我们使用了"def"的第二个"e",就进入了第六次递归调用

findCombination(digits,2,"ae");

此时打印了

2 : ae

然后我们要从digtis[2]进行处理,digits[2]等于'4','4'在letterMap中代表了"ghi",我们使用了"ghi"的第一个"g",就进入了第七次递归调用

findCombination(digits,3,"aeg");

到这里后面的我们就不再分析了。

用图示的方式来表示,就是这样一棵树(假设我们初始为"23")

这种算法的时间复杂度为    3^n = O(2^n)

它表示的是一种指数级增长的趋势,如果初始的字符串达到长度为20的时候,对于我们的常用计算机就可能无法处理了。

贪心算法篇

在求解一个最优化的问题中,我们使用贪心的方式选择了一组内容之后,不会影响剩下的子问题的求解。对于一个问题是否满足贪心选择性质,其实去验证是比较难的。如果无法使用贪心算法,举出反例即可。

比如给出一个正整数n,寻找最少的完全平方数,使他们的和为n.

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

如果对12使用贪心算法 12 = 9 + 1 + 1 + 1 则明显有12 = 4 + 4 +4比9加三个1要少,所以贪心算法不成立

如果无法举出反例,如何证明贪心算法的正确性——反证法。

我们先来看一道区间的题目

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

我们先使用动态规划法来解决这个问题

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++) {
            memo.add(1);
        }
        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. 结尾越小,留给了后面越大的空间,后面越有可能容纳更多区间。

此时动态规划的时间复杂度为O(n^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;
        }
    }
}

贪心算法的时间复杂度为O(n)级别的。

现在我们使用反证法来证明这个贪心算法:按照区间的结尾排序,每次选择结尾最早的,且和前一个区间不重叠的区间。

某次选择的是[s(i),f(i)];其中f(i)是当前所有选择中结尾最早的。

假设这个选择不是最优的。也就是说,如果这个问题的最优解为k,则这个选择得到的解,最少为k - 1。

假设最优解在这一步[s(j),f(j)]中,f(j) > f(i)。

此时,显然可以将[s(i),f(i)]替换[s(j),f(j)],而不影响后续的区间选择。

此时,当我们选择[s(i),f(i)]时,也构成了一个大小为k的解。

假设这个选择不是最优的。也就是说,如果这个问题的最优解为k,则这个选择得到的解,最多为k - 1。

矛盾!这个问题具有贪心选择性质。

贪心选择性质的证明

贪心算法为A;最优算法为O;发现A完全能替代O,且不影响求出最优解。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部