动态规划(Dynamic Programming)

动态规划其实和分治策略是类似的,也是将一个原问题分解为若干个规模较小的子问题,递归的求解这些子问题,然后合并子问题的解得到原问题的解。 区别在于这些子问题会有重叠,一个子问题在求解后,可能会再次求解,于是我们想到将这些子问题的解存储起来,当下次再次求解这个子问题时,直接拿过来就是。 其实就是说,动态规划所解决的问题是分治策略所解决问题的一个子集,只是这个子集更适合用动态规划来解决从而得到更小的运行时间。 即用动态规划能解决的问题分治策略肯定能解决,只是运行时间长了。因此,分治策略一般用来解决子问题相互对立的问题,称为标准分治,而动态规划用来解决子问题重叠的问题。

动态规划 的概念关键点抽离出来描述就是这样的:

  • 动态规划法试图只解决每个子问题一次。

  • 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。

爬楼梯问题

下面通过爬楼梯问题来分析使用动态规划的解决问题(该问题也是在现场面试中遇到的)。

问题描述:爬楼梯,我们每次可以走 1 级阶梯或者 2 级阶梯,那我们走 50(n) 级阶梯总共有多少种走法。 在现场思考过程中,如果没有使用动态规划的话,那就要用递归的概念去做。

递归方式

我们在高中的数学课里面应该学习过规律推理,那我们可以很容易的去推理出来公式: 1 级台阶: 1 种走法(f(1)) 2 级台阶: 2 种走法(f(2)) 3 级台阶: 3 种走法(f(3) = f(2) + f(1)) 4 级台阶: 5 种走法(f(4) = f(3) + f(2)) 5 级台阶: 8 种走法(f(5) = f(4) + f(3)) ... n 级台阶: f(n) = f(n-1) + f(n-2) (n > 2)

通过以上公式,很容易推导出一下递归代码:

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

code:

int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    // a 保存倒数第二个子状态数据,b 保存倒数第一个子状态数据, temp 保存当前状态的数据
    int a = 1, b = 2;
    int temp = a + b;
    for (int i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp; 
    }
    return temp; 
}

从递归到动态规划

还是以爬台阶为例,如果以递归的方式解决的话,那么这种方法的时间复杂度为O(2^n)

详解动态规划

动态规划中包含三个重要的概念:

  • 最优子结构

  • 边界

  • 状态转移公式

爬台阶问题中:

f(10) = f(9) + f(8) 是最优子结构 f(1) 与 f(2) 是边界 f(n) = f(n-1) + f(n-2) 状态转移公式

爬台阶问题只是动态规划中相对简单的问题,因为它只有一个变化维度,如果涉及多个维度的话,那么问题就变得复杂多了。

难点就在于找出动态规划中的这三个概念。感觉跟我们高中学习的推理证明题有点像,通过现在的条件推断出结果。

国王和金矿问题

问题描述

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

Last updated