动态规划和贪婪算法

剪绳子问题

有一根长度为 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;
  }
}