Ex14-1 剪绳子

题目描述

给你一根长度为 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。

解题思路

这题的方法基本上就是动态规划了，这里有一个小注意点是m>1，当n=2时，结果应该得到1.

代码

int
cuttingRope (int n)
{
  if (n < 2)
    return 0;
  if (n == 2)
    return 1;
  if (n == 3)
    return 2;
  int a[n + 1];
  a[0] = 0;
  a[1] = 1;
  a[2] = 2;
  a[3] = 3;
  for (int i = 4; i <= n; ++i)
    {
      int max = 1;
      for (int j = 1; j <= i / 2; ++j)
        {
          max = (max > a[j] * a[i - j]) ? max : a[j] * a[i - j];
        }
      a[i] = max;
    }
  return a[n];
}

结果

执行结果：通过

执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户

内存消耗：5.5 MB, 在所有 C 提交中击败了13.01%的用户

备注

从《剑指offer》上的tip上说了一个更简单的方法。将绳子尽量剪更多的长度为3的段，并且如果最后能剩下4的话，则不再剪（或剪成2*2）。根据这个tip，作者写下了以下的代码，但是不知为何，内存消耗仍是5.4MB。

int
cuttingRope (int n)
{
  if (n < 2)
    return 0;
  if (n == 2)
    return 1;
  if (n == 3)
    return 2;
  int ret = 1;
  while (n - 3 >= 0)
    {
      if (n == 4)
        {
          ret *= 4;
          n = 0;
        }
      else
        {
          ret *= 3;
          n -= 3;
        }
    }
  if (n)
    {
      ret *= n;
    }
  return ret;
}