跳转至

4.4 动态规划与贪婪算法

动态规划现在是编程面试中的热门话题。 如果面试题是求一个问题的最优解(通常是最大值或者最小值),而且该问题能够分解成若干个子问题,并且子问题之间还有重叠的更小的子问题,就可以考虑用动态规划来解决这个问题。

我们在应用动态规划之前要分析能否把大问题分解成小问题,分解后的每个小问题也存在最优解,如果把小问题的最优解组合起来能够得到整个问题的最优解,那么我们可以应用动态规划解决这个问题。

动态规划的4个特点

例如在面试题14中,我们如何把长度为 n 的绳子剪成若干段,使得得到各段长度的乘积最大。 这个问题的目标是求剪出的各段绳子长度的乘积最大值,也就是 求一个问题的最优解,这是可以应用动态规划求解问题的第一个特点。

我们把长度为 n 的绳子剪成若干段后得到的乘积最大值定义为函数f(n); 假设我们把第一刀剪在长度为i (0 < i < n) 的位置,于是把绳子剪成了长度分别为 i 和 n - i 的两段。 我们要想得到整个问题的最优解 f(n), 那么要同样用最优解的方法把长度为i和n-i 的两段分成剪成若干段,使得它们各自剪出的每段绳子的长度乘积最大,也就是说 整体问题的最优解是依赖各个子问题的最优解,这是可以应用动态规划求解的问题的第二个特点。

我们可以把大问题分解成若干个小问题,这些小问题之间还有相互重叠的更小子问题。

由于子问题在分解大问题的过程中重复出现,为了避免重复求解子问题,我们可以用从下往上的顺序先计算小问题的最优解并存储下来,再以此为基础求取大问题的最优解, 从下往上求解问题, 这是可以应用动态规划求解问题的第四个特点.

贪婪算法

当我们应用贪婪算法解决问题的时候, 每一步都可以做出一个贪婪的选择, 基于这个选择, 我们确定能够得到最优解.

面试题14: 剪绳子

Question

给你一根长度为n 的绳子, 请把绳子剪成m 段(m, n, 都是整数, n > 1, m > 1), 每段绳子的长度记为k[0], k[1], ... k[m], 请问k[0]*k[1]*...*k[m]可能的最大乘积是多少? 例如, 当绳子长度为8时, 我们把它剪成长度为2, 3, 3的三段, 此时得到的最大乘积为18.

Tip

解法1: 动态规划

首先定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值, 在剪第一刀的时候, 我们有n - 1 种选择, 也就是剪出来的第一段绳子的可能长度分别为, 1, 2, ... n - 1, 因此 f(n) = max(f(i) * f(n - i)) 其中 0 < i < n.

这是一个从上至下的递归公式, 由于递归会有很多重复的子问题, 从而有大量不必要的重复计算, 一个更好的办法就是按照从下而上的顺序计算, 也就是我们先得到f(2), f(3), 再得到f(4), f(5), 直到得到f(n); 当绳子长度为2时, 只可能剪成长度都为1的两段, 因此f(2) 等于1, 当绳子长度为3时, 可能把绳子剪成长度为1,2的两段或者长度都为1的三段, 由于1*2 > 1*1*1, 因此f(3) = 2

Answer

解法1:

int getCutLineMultiMax(int length)
{
    if (length < 2)
        return 0;

    if (length == 2)
        return 1;

    if (length == 3)
        return 2;

    int* products = new int[length + 1];
    memset(products, 0, (length + 1) * sizeof(4));
    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;

    for (int i = 4; i <= length; i++)
    {
        for (int j = 1; j <= i / 2; j++)
        {
            int product = products[j] * products[i - j];
            if (product > products[i])
            {
                products[i] = product;
            }
        }
    }
    int res = products[length];
    delete[] products;
    return res;
}
完整代码: 剪绳子