算法,爬楼梯问题

436 阅读12分钟
原文链接: chenjianhui.site

有一座高度是1000级台阶的天梯,从下往上走,每跨一步只能向上1级或者2级台阶。要找出一共有多少种走法?

解题思考

  如题1000级台阶着实有点多了,我们先来思考6级阶梯的情况,共13种

  • 🏃 1+1+1+1+1+1
  • 🏃 1+1+1+1+2
  • 🏃 1+1+1+2+1
  • 🏃 1+1+2+1+1
  • 🏃 1+2+1+1+1
  • 🏃 2+1+1+1+1
  • 🏃 1+1+2+2
  • 🏃 1+2+1+2
  • 🏃 1+2+2+1
  • 🏃 2+1+1+2
  • 🏃 2+1+2+1
  • 🏃 2+2+1+1
  • 🏃 2+2+2

  在仅有6级阶梯的情况下穷举已经有一些费力了,如果是1000级那几乎不可能穷举了,我们要思考找出其中的微妙之处。
  现在我们假设只差最后一步就能达到第6级阶梯了,那么会出现几种情况?无非就是从第5级花费一步或者从第4级花费两步跳到第6级阶梯,我们现在假设0-4级阶梯有X种走法,0-5级阶梯有Y种走法,那么0-6级阶梯的走法有多少种?

🏃差一步 ==6级==
🏃差两步 ==5级== ?种走法🐴
==4级== Y种走法🐴
==3级== X种走法🐴
==2级==
==1级==

  我们来分析一下,要走到第6级阶梯最后一步必然从4或5级阶梯开始的,而4或5级阶梯我们知道它的走法为X与Y,那么显然0-6级阶梯的走法即为X+Y,这个时候我们可以发现,每一级阶梯的走法数目其实都是由它的前两级阶梯来决定的,即可用此函数表示

fun(N) = func(N - 1) + func(N - 2)

  且我们知道第1级的阶梯有一步走法,第二级的阶梯有两步走法,所以函数完整的表示为

func(1) = 1
func(2) = 2
fun(N) = func(N - 1) + func(N - 2)

  这种解题思路即是动态规划思想,将大事化小,小事化了,转换为简单的问题,其中最后一步必然从4或5级阶梯开始这个称之为最优子结构,上述的方程称之为状态转移方程,func(1|2)称之为边界

编码实现

递归实现

  上述的方程随眼一看即知道,这是一个递归方程,现在我们使用递归编程来实现此题的解法。

public int getStairsWays(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return n;
    }
    return getStairsWays(n - 1) + getStairsWays(n - 2);
}

  其实稍微计算一下这套实现的时间复杂度你就会发现非常恐怖,它的计算量相当于一个二叉树,时间复杂度达到了O(2^N),空间复杂度为O(1)。这道题目的优化空间是很大的,我们首先思考一下它的计算过程,我们可以发现很多都是重复计算的

func(5) = func(4) + func(3)

func(4) = func(3) + func(2)

func(3) = func(2) + func(1)

  func(3)被重复计算了很多次,为了降低计算次数,我们可以将已经计算过的缓存起来,不去重新计算它。

备忘录算法

  备忘录算法是递归实现了一种改良版,使用了一块内存区域来存储已经计算过的阶梯数,防止重复计算,在这里使用的是HashMap对象,其实更优的选择应该是一个长度为阶梯高度的int数组。

public int getStairsWays(int n) {
    return getStairsWays(n, null);
}

public int getStairsWays(int n, Map<Integer, Integer> cache) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return n;
    }
    if (cache == null) { // 初始化一个缓存对象 容量为log(n)的向上取整
        cache = new HashMap<>((int) Math.ceil(Math.log(n) / Math.log(2)));
    }
    if (cache.containsKey(n)) {
        return cache.get(n);
    }
    int value = getStairsWays(n - 1, cache) + getStairsWays(n - 2, cache);
    cache.put(n, value);
    return value;
}

  我们大概看一下这个算法的时间与空间复杂度,备忘录缓存了各级背包的计算结果因此它真正计算的只有n次,时间复杂度为O(N),由于需要内存去缓存计算结果,所以它的空间复杂度也为O(N)
  我们可以再分析一下,还有没有更优的解法呢?重新观察我们的计算过程

func(6) = func(5) + func(4)

func(5) = func(4) + func(3)

func(4) = func(3) + func(2)

func(3) = func(2) + func(1)

  func(6)只依赖于func(5)与func(4),所以当func(5)与func(4)的结果值出来以后,func(3)这个结果就再没必要缓存了,我们把思维逆转一下,从func(3)开始计算到func(6)。

动态规划算法

  这里我们考虑使用自底向上的解法,只需要用两个变量来存储它的两个依赖值,分别是差两步的走法数目(pre)以及差一步的走法数目(next),最终的走法数目为这两个依赖值的和。

public int getStairsWays(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return n;
    }
    int pre = 1;
    int next = 2;
    for (int i = 3; i < n; i++) {
        int temp = next;
        next = pre + next;
        pre = temp;
    }
    return pre + next;
}

  分析一下这个算法的时间与空间复杂度,循环n-2次计算,所以时间复杂度是O(N),内存上只开辟了两个临时变量没有额外的内存空间使用,所以空间复杂度为O(1),这就是真正的动态规划算法。
  有兴趣的同学可以测试一下以上三个算法在1000个阶梯的量级下运行时间,反正我使用递归运行了一下1000次阶梯,等了十分钟也没结果最终放弃了…

有没有更优解

  答案是有的,且时间复杂度为O(logN),有兴趣的可以搜索数论中的矩阵快速幂,可根据状态转移方程快速计算出结果,与动态规划思想结合使用。
  还有就是我们来观察上面讲到的状态转移方程,不难看出这表示的是一个斐波那契数列,而斐波那契数列是有通项公式的,在如这种特定问题下可以直接代入通项公式求解。

题目扩展, 背包问题

  给定一组多个(n)物品,每种物品都有自己的重量(Wi)和价值(Vi),每种物品至多选择一个,在限定可承受总重量(C)的背包内,要想背包内物品的总价值最高,应该选择那几件物品?

简化题目

  我们先假设有5组物品,其中它的价值与重量分别为[4,2,1,3,1]、[4,3,2,1,2],背包可承受总重量为6,求应该选那几件物品使得背包中的物品价值最大?

动态规划思路四步解题

问题是否可拆分

  如爬楼梯问题可以拆分成剩余一步与剩余两步的走法,此问题该如何拆分?

  • 我们先针对最后一个物品(价值为1,重量为2)做假设
    (1) 装载物品进入背包,问题演变成,有4组物品,背包承重量为4,应该选那几件物品使得背包中的物品价值最大?
    (2) 物品不被装载,问题演变成,有4组物品,背包承重量为6,应该选那几件物品使得背包中的物品价值最大?
    (3) 接下来我们还可以对子情况(1)、(2)分别做假设,因此该问题是可拆分的

最优子结构是什么?

  如爬楼梯的问题的最优子结构是剩余一步与剩余两步的走法相加,此问题的最优结构是什么?

  针对我们刚刚的假设(1)、(2),要想使得背包物品价值最大,最优的结构显而易见是(1)、(2)情况中背包价值更大的那个方案。

状态转移方程是什么?

  • 问题拆分及找出最优子结构后,状态转移方程就很好推导了,存在两种情况
    (1) 背包容量大于等于下一个物品的重量:物品存在选择与不选两种情况
    (2) 背包容量小于下一个物品重量:物品不可被选择,情况只有一种

  可得背包问题的状态转移方程为

func(n, c) = max(func(n - 1, c - W[n - 1]) + V[n - 1], func(n - 1, c)) (n > 1, c >= W[n - 1])
func(n, c) = func(n - 1, c) (n > 1, c < W[n - 1])

其中
n => 剩余物品数量
c => 背包剩余容量
W => 物品重量数组
V => 物品价值数组

边界是什么?

  问题不断的向子问题拆分后一定会有一个头,如爬楼梯是将一阶和二阶楼梯作为边界,针对背包问题,它的边界是什么?

  • 不难想到,当只剩最后一个物品,此时没有多余的物品能够选择了,就只能选择此物品,而选择此问题有两种情况
    (1) 背包容量大于等于物品重量:此时返回物品价值
    (2) 背包容量小于物品重量:此时返回0

  可得背包问题的边界为

func(1, c) = V[0] (n = 1, c >= W[0])
func(1, c) = 0 (n = 1, c < W[0])

编码实现

简单递归

/**
 * 获取最大价值
 *
 * @param n 物品数量
 * @param c 背包剩余承重量
 * @param w 物品重量
 * @param v 物品价值
 * @return 背包装配物品的最大价值
 */
int getMaxValues(int n, int c, int[] w, int[] v) {
    if (n == 1) { // 边界
        if (c >= w[0]) {
            return v[0];
        } else {
            return 0;
        }
    }
    if (c >= w[n - 1]) { // 状态转移公式
        return Math.max(getMaxValues(n - 1, c - w[n - 1], w, v) + v[n - 1],
                getMaxValues(n - 1, c, w, v));
    } else {
        return getMaxValues(n - 1, c, w, v);
    }
}

备忘录算法

int getMaxValues(int n, int c, int[] w, int[] v) {
    return getMaxValues(n, c, w, v, null);
}

int getMaxValues(int n, int c, int[] w, int[] v, Map<String, Integer> cache) {
    if (n == 1) { // 边界
        if (c >= w[0]) {
            return v[0];
        } else {
            return 0;
        }
    }
    if (cache == null) {
        cache = new HashMap<>((int) Math.ceil(Math.log(n) / Math.log(2)));
    }
    if (cache.containsKey(generatorCacheKey(n, c))) {
        return cache.get(generatorCacheKey(n, c));
    }
    int value;
    if (c >= w[n - 1]) { // 状态转移公式
        value = Math.max(getMaxValues(n - 1, c - w[n - 1], w, v, cache) + v[n - 1],
                getMaxValues(n - 1, c, w, v, cache));
    } else {
        value = getMaxValues(n - 1, c, w, v, cache);
    }
    cache.put(generatorCacheKey(n, c), value);
    return value;
}

String generatorCacheKey(int n, int c) {
    return String.format("%s_%s", n, c);
}

动态规划算法

  跟爬楼梯问题一样,我们自底向上来思考这个问题,我们不妨基于简化的问题画一个表格来分析这个情况,表格第一列表示5个物品的情况,括号内代表价值与重量,表格的第一行表示给予的背包容量,其余的空白格子代表背的最大价值数。

  简化的问题:有5组物品,其中它的价值与重量分别为[4,2,1,3,1]、[4,3,2,1,2],背包可承受总重量为6。

剩余1容量 剩余2容量 剩余3容量 剩余4容量 剩余5容量 剩余6容量
物品1 (4,4)
物品2 (2,3)
物品3 (1,2)
物品4 (3,1)
物品5 (1,2)

  第一行非常容易填写,只有一个物品的情况下,背包最大价值要么为0要么为4,各自中箭头前面描述的是选择了那几个物品。

剩余1容量 剩余2容量 剩余3容量 剩余4容量 剩余5容量 剩余6容量
物品1 (4,4) 0 0 0 1 => 4 1 => 4 1 => 4
物品2 (2,3)
物品3 (1,2)
物品4 (3,1)
物品5 (1,2)

  我们将其余的格子全部填写完成,接下来的这几段很重要,理解它就理解了动态规划算法的核心。

物品(v,w)/c 剩余1容量 剩余2容量 剩余3容量 剩余4容量 剩余5容量 剩余6容量
物品1 (4,4) 0 0 0 1 => 4 1 => 4 1 => 4
物品2 (2,3) 0 0 2 => 2 1 => 4💧 1 => 4 1 => 4💧
物品3 (1,2) 0 3 => 1 2 => 2 1 => 4🌙 1 => 4🌙 1,3 => 5🌀
物品4 (3,1) 4 => 3 4 => 3 3,4 => 4 1,3 => 5 1,4 => 7 1,4 => 7
物品5 (1,2) 4 => 3 4 => 3 3,4 => 4 1,3 => 5 1,4 => 7 1,4 => 7
  • 我们来找一下规律

    • 先回顾一下核心的状态转移方程

      func(n, c) = max(func(n - 1, c - W[n - 1]) + V[n - 1], func(n - 1, c))
    • 我们先看🌀/💧这个图标组合,做一个方程代入

      n = 3 , c = 6 , V[2] = 1 , W[2] = 2
      注意,这里V[2]、W[2]对应的是物品3,因为数组从0开始编号
      func(3, 6) = max(func(2, 4) + 1 , func(2, 6))
    • 再看⭐/🌙这个图标组合,做一个方程代入

      n = 4 , c = 5 , V[3] = 3 , W[3] = 1
      func(4, 5) = max(func(3, 4) + 3 , func(3, 5))

  规律已经很明显了,每个格子的数据都只依赖于它的前一行数据,和爬楼梯中我们最后只存储了前两步数据的思路一样,在这里我们只需要存储前一行的数据即可推导出下一行的数据,编码的思路和我们填充表格的思路一致,代码如下:

int getMaxValues(int n, int c, int[] w, int[] v) {
    int[] pre = new int[c + 1]; // 前一行
    int[] current = new int[c + 1]; // 当前行
    for (int i = 1; i <= c; i++) { // 先填充第一行
        if (i < w[0]) {
            pre[i] = 0;
        } else {
            pre[i] = v[0];
        }
    }

    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= c; j++) { // 填充第二行到最后
            if (j < w[i]) { // 容量不够
                current[j] = pre[j];
            } else {
                current[j] = Math.max(pre[j - w[i]] + v[i], pre[j]);
            }
        }
        // 此处不可直接使用等号 会出现引用混乱的情况
        pre = Arrays.copyOf(current, current.length);
    }
    return current[c];
}

题目扩展,采金矿

  有一个国家发现了n座金矿,每座金矿的黄金储量(Vi)不同,需要参与挖掘的工人数(Li)也不同。参与挖矿工人的总数是C人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要想得到尽可能多的黄金,应该选择挖取哪几座金矿?

  此题是背包问题的变种,解题思路是一样的,有兴趣的同学可以自己思考一下。