动态规划和贪心

剪绳子

有一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n 都是整数，n > 1 并且 m > 1），每段绳子的长度记为 k[0],k[1]…k[m-1]请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？如，当绳子的长度是 8 时，把它剪成 2、3、3 三段，此时得到的最大乘积是 18。

动态规划

介绍

动态规划是编程面试中的热门话题，如果求一个问题的最优解（通常是最大值或最小值），同时该问题能够分解成若干个子问题，且子问题之间还有重叠的更小子问题，可以考虑用动态规划来解决问题。

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

• 如何把长度为 n 的绳子剪成若干段，使得得到的各段长度的乘积最大。这个问题的目标是求剪出的各段绳子长度的乘积最大值：求一个问题的最优解 => 应用动态规划求解问题的第一个特点

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

• 假设绳子最初长度为 10，我们可以把绳子剪成长度分别为 4 和 6 的两段，也就是 f(4) 和 f(6) 都是 f(10) 的子问题。接下来分别求解这两个子问题。我们可以把长度为 4 的绳子剪成均为 2 的两段，即 f(2) 是 f(4) 的子问题。同样，我们也可以把长度为 6 的绳子剪成长度分别为 2 和 4 的两段，即 f(2) 和 f(4) 都是 f(6) 的子问题。注意到， f(2) 是 f(4) 和 f(6) 公共的更小的子问题：把大问题分解成若干个小问题，这些小问题之间还有相互重叠的更小的子问题 => 应用动态规划求解的问题的第三个特点

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

在应用动态规划解决问题的时候，我们总是从解决最小问题开始，并把已经解决的子问题的最优解存储下来(大部分面试题都是存储在一维或者二维数组里)，并把子问题的最优解组合起来逐步解决大的问题。

在应用动态规划的时候，我们每一步都可能面临若干个选择。由于我们不知道哪个才是最优的解法，只好把所有的可能都尝试一遍，然后比较得出最优方法。如果用数学的语言来表示，这就是 f(n) = max(f(i)×(n-i))，其中 0 < i < n。

function cuttingRope(n) {
  const dp = new Array(n + 1).fill(1);
  for (let i = 3; i <= n; i++) {
    for (let j = 1; j < i; j++) {
      dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
    }
  }
  return dp[n];
}

总结

动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。

对比

子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同：

• 分治递归地将原问题分为多个相互独立的子问题直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
• 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题相互依赖，在分解过程中会出现许多重叠子问题。
• 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，可以将每个决策步骤之前的子序列看作一个子问题。

贪心

介绍

当用贪心解决问题时，每一步都可以做出一个贪婪的选择，即贪心地做出局部最优的决策，以期获得全局最优解。为什么这样的贪婪选择能够得到最优的解？需要用数学方式来证明贪婪选择是正确的。贪心和动态规划都常用于解决优化问题。它们之间存在一些相似之处，比如都依赖最优子结构性质，但工作原理不同：

• 动态规划会根据之前的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解
• 贪心不会考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决

如果绳子的长度大于 5，则每次都需剪出一段长度为 3 的绳子。如果剩下的绳子的长度仍然大于 5，接着剪出一段长度为 3 的绳子。重复这个步骤，直到剩下的绳子的长度小于 5。剪出一段长度为 3 的绳子，就是我们在每一步做出的贪婪选择。为什么这样的贪婪选择能得到最优解？这是应用贪心时，都需要问的问题：需要用数学方式来证明贪婪选择是正确的。

首先，当 n ≥ 5 的时候，我们可以证明 2(n - 2) > n 并且 3(n - 3) > n。也就是说，当绳子剩下的长度大于或者等于 5 的时候，我们就把它剪成长度为 3 或者 2 的绳子段。另外，当 n ≥ 5 时 3(n - 3) ≥ 2 (n - 2)，因此我们应该尽可能地多剪长度为 3 的绳子段。前面证明的前提是 n ≥ 5。那么当绳子的长度为 4 呢？在长度为 4 的绳子上剪一刀，有两种可能的结果: 2 × 2 > 1 × 3，同时 2 × 2 = 4，也就是说，当绳子长度为 4 时其实没有必要剪，只是题目的要求是至少要剪一刀。

function cuttingRope(n) {
  if (n <= 3) return n - 1;
  // 下面内容可以加上也可以去掉
  // else if (n == 4) {
  //   return 4
  // }
  else {
    let num = 0;
    while (n >= 5) {
      n = n - 3;
      num++;
    }
    return Math.pow(3, num) * n;
  }
}

或

function cuttingRope(n) {
  if (n <= 3) {
    return n - 1;
  } else if (n % 3 === 0) {
    return 3 ** (n / 3);
  } else if (n % 3 === 1) {
    return 3 ** (Math.floor(n / 3) - 1) * 2 * 2;
  } else if (n % 3 === 2) {
    return 3 ** Math.floor(n / 3) * 2;
  }
}

适用

一般情况下，贪心算法的适用情况分以下两种：

• 可以保证找到最优解：贪心在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效
• 可以找到近似最优解：贪心在这种情况下也是可用的。对于很多复杂问题来说，寻找全局最优解非常困难，能以较高效率找到次优解也是非常不错的

相较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质：

• 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解
• 最优子结构：原问题的最优解包含子问题的最优解

探究贪心选择性质的判断方法，虽然描述看上去比较简单，但是实际上对于许多问题，证明贪心选择性质并非易事。