动态规划快速入门

Java基础

浏览数:192

2019-9-2

更多内容,欢迎关注微信公众号:全菜工程师小辉。公众号回复关键词,领取免费学习资料。

动态规划算法一直是面试手撕算法中比较有挑战的一种类型。很多的分配问题或者调度问题实际上都可能用动态规划进行解决。(当然,如果问题的规模较大,有时候会抽象模型使用动归来解决,有时候则可以通过不断迭代的概率算法解决查找次优解)

所以,动归很重要,至少算法思想很重要。

什么是动态规划?

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。

重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。

不理解不用怕,结合后面题目来理解这些概念。这些概念完全是已经会动归的人来总结出来的,所以先理解动归,然后再来看这些文绉绉的概括。

分治与动态规划

共同点:
二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决)的子问题。然后将子问题的解合并,形成原问题的解。

不同点:

  • 分治法将分解后的子问题看成相互独立的,通过用递归来做。
  • 动态规划将分解后的子问题理解为相互间有联系,有重叠部分,需要记忆,通常用迭代来做。

动态规划的步骤

问题建模

  1. 根据问题,找到【最优子结构】。把原问题从大化小的第一步,找到比当前问题要小一号的最好的结果,而一般情况下当前问题可以由最优子结构进行表示。
  2. 确定问题的【边界】。根据上述的最优子结构,一步一步从大化小,最终可以得到最小的,可以一眼看出答案的最优子结构,也就是边界。
  3. 通过上述两步,通过分析最优子结构与最终问题之间的关系,我们可以得到【状态转移方程】。

    问题求解的各个方法

    暴力枚举:

    所有的动态规划问题都可以通过多层嵌套循环遍历所有的可能,将符合条件的个数统计起来。只是时间复杂度是指数级的,所以不推荐。

递归:

  1. 递归的时间复杂度是由递归层数和最优子结构的个数决定的。
  2. 在爬阶梯问题,最少找零钱问题中,递归的时间复杂度和空间复杂度都比动归方法的差,但是在国王与金矿的问题中,不同的数据规模,动归方法的时间复杂度和空间复杂度不一定比递归的要好。所以具体问题具体分析。

上面提到的三个问题是动态规划里很常见的题目,题目内容可以百度查看一下。篇幅原因,本文后边只讲解前两道题

备忘录算法:

  1. 在阶梯数N比较多的时候,递归算法的缺点就显露出来了:时间复杂度很高。如果画出递归图(像二叉树一样),会发现有很多很多重复的节点。然而传统的递归算法并不能识别节点是不是重复的,只要不到终止条件,它就会一直递归下去。
  2. 为了避免上述情况,使递归算法能够不重复递归,就把已经得到的节点都存起来,下次再遇到的时候,直接用存起来的结果就行了。这就是备忘录算法。
  3. 备忘录算法的时间复杂度和空间复杂度都得到了简化。

动态规划算法:

  1. 上述的备忘录算法,尽管已经不错了,但是依然还是从原问题,遍历得到所有的最小子问题,空间复杂度是O(N)。
  2. 为了再次缩小空间复杂度,我们可以自底向上的构造递归问题,通过分析最优子结构与最终问题之间的关系,我们可以得到【状态转移方程】。
    然后从最小的问题不断往上迭代,即使一直迭代到最大的原问题,也是只依赖于前面的几个最优子结构。这样,空间复杂度就大大简化。也就得到了动归算法算法。

例题

例1: Climbing Stairs(爬楼梯问题)
leetcode原题:你正在爬一个有n个台阶的楼梯,每次只能上1个或者2个台阶,那么到达顶端共有多少种不同的方法?

  1. 建立模型:
  • 最终问题F(N):假设从0到达第N个台阶的方法共有F(N)个。
  • 最优子结构F(N-1),F(N-2):到达N个台阶,有两种可能,第一种可能是从第 N-1 个台阶上1个台阶到达终点,第二种可能是从第 N-2 个台阶上2个台阶到达终点。
  • 最优子结构与最终问题之间的关系:按照上述表达,那么可以归纳出F(N) = F(N-1) + F(N-2) (n>=3)
  • 边界:F(1) = 1,F(2) = 2
  1. 问题求解:
  • 递归:
class Solution {
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        } else {
            return climbStairs(n - 1) + climbStairs(n - 2);
        }
    }
}

递归的时间复杂度是由递归层数和最优子结构的个数决定的。这里的阶梯数是 N ,最优子结构个数是2。如果想象成一个二叉树,那么就可以认为是一个高度为N-1,节点个数接近2的N-1次方的树,因此此方法的时间复杂度可以近似的看作是O(2N) 。

  • 备忘录算法:
    这里我们想到了把重复的参数存储起来,下次递归遇到时就直接返回该参数的结果,也就是备忘录算法了,最简单的备忘录就是哈希表。
class Solution {
    private Map<Integer, Integer> map = new HashMap<>();

    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        } else if (map.containsKey(n)) {
            return map.get(n);
        } else {
            int value = climbStairs(n - 1) + climbStairs(n - 2);
            map.put(n, value);
            return value;
        }
    }
}
  • 动态规划:
    之前都是自顶向下的求解,考虑一下自底向上的求解过程。从F(1)和F(2)边界条件求,可知F(3) = F(1)+F(2)。不断向上,可知F(N)只依赖于前两个状态F(N-1)和F(N-2)。于是我们只需要保留前两个状态,就可以求得F(N)。相比于备忘录算法,我们再一次简化了空间复杂度。
class Solution {
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        // 边界条件
        int a = 1;
        int b = 2;
        int result = 0;
        // 最优子结构与最终问题之间的关系
        for (int i = 3; i <= n; i++) {
            result = a + b;
            a = b;
            b = result;
        }
        return result;
    }
}

空间复杂度O(1), 时间复杂度O(N)

例2: Making change using the fewest coins(最少找零钱问题)
Google面试题:假设你是一家自动售货机制造商的程序员。你的公司正设法在每一笔交易 找零时都能提供最少数目的硬币以便工作能更加简单。已知硬币有四种(1美分,5美分,10美分,25美分)。假设一个顾客投了1美元来购买37美分的物品 ,你用来找零的硬币的最小数量是多少?

  1. 建立模型:
  • 最优子结构:回想找到最优子结构的方法,就是往后退一步,能够得到的最好的结果。这里有四个选择,1 + mincoins(63-1),1 + mincoins(63-5),1 + mincoins(63-10) 或者 1 + mincoins(63-25),这四个选择可以认为是63的最优子结构。
  • 状态转移方程:按照上述的最优子结构,mincoins(63)也就等于上述四个最优子结构的最小值。
  • 边界: 当需要找零的面额正好等于手中单枚硬币的金额时,返回1即可。
  1. 问题求解:
  • 递归:
class Solution {
    Set<Integer> coinSet = new HashSet<Integer>() {
        {
            add(1);
            add(5);
            add(10);
            add(25);
        }
    };

    int getFewestCoins(int n) {
        if (n < 1) {
            return 0;
        }
        if (coinSet.contains(n)) {
            return 1;
        }
        int minCoins = n;
        int numCoins = Integer.MAX_VALUE;

        for (int coin : coinSet) {
            if (n >= coin) {
                // 如果要计算的n小于单个硬币金额,则不能出现在状态转移方程中
                numCoins = 1 + getFewestCoins(n - coin);
            }
            // 更新最小值
            if (numCoins < minCoins) {
                minCoins = numCoins;
            }
        }
        return minCoins;
    }
}
  • 备忘录算法:
    就是将递归里计算的中间变量都保存在一个哈希表,代码略。

  • 动态规划:
    自底向上,从找零数等于1开始往上迭代,参考最优子结构,记录下来最少硬币数。一直迭代到实际要求。

class Solution {
    Set<Integer> coinSet = new HashSet<Integer>() {
        {
            add(1);
            add(5);
            add(10);
            add(25);
        }
    };

    int getFewestCoins(int n) {
        int[] list = new int[n + 1];
        List<Integer> subCal = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            // 边界
            if (i <= 1) {
                list[i] = i;
                continue;
            }
            for (int cent : coinSet) {
                if (i >= cent) {
                    subCal.add(list[i - cent] + 1);
                }
            }
            list[i] = Collections.min(subCal);
            subCal.clear();
        }
        return list[n];
    }
}

更多内容,欢迎关注微信公众号:全菜工程师小辉。公众号回复关键词,领取免费学习资料。

作者:全菜工程师小辉