剪绳子 | Eric's Blogs

题目描述

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

输入描述:

1	输入一个数n，意义见题面。（2 <= n <= 60）

输出描述:

输出答案。

示例1

输入

输出

解答

得到最大值的m值是距离sqrt(target)最近的两个整数.讨论这两种情况即可.

数学证明待补充

public int cutRope(int target) {
    if (target <= 3) {
        return target - 1;
    }
    int m = (int) Math.floor(Math.sqrt(target));

    int k1 = target / m, mult1 = 1;
    int i = 0;
    for (; i < m - 1; i++) {
        mult1 *= k1;
    }
    int remain = target - k1 * i;
    mult1 *= remain;

    m++;
    int k2 = (target / m) + 1, mult2 = 1;
    for (i = 1; i * k2 <= target; i++) {
        mult2 *= k2;
    }
    remain = target - k2 * i;
    if (remain != 0) {
        mult2 *= remain;
    }
    return mult1 > mult2 ? mult1 : mult2;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?answerType=1&f=discussion
来源：牛客网

题目描述：给定一个长度为n的绳子，将其分成m段（m>1）,求m段的乘积最大。
转化成数学上的描述：给定一个数n，求n = a1 + a2 … +am, （m>1）在此条件下, s = a1 * a2 * … * am， s最大

进入此题的讲解之前，先提出一个问题：什么样的题适合用动态规划？
针对本题来说，假如我们用暴力枚举的思路去思考，会出现以下一些问题：

这段绳子到底应该分几段，才能得到最优的结果？
假设我已经知道了要分m段（假设m已知），那么每段的长度又应该是多少呢？

可能你的问题不止上面2个。但是，仅仅是上面两个问题，已经让我感觉要分好多种情况，然后选出一个最优的。

当然，普通的for循环枚举所有情况是有难度的，但是幸运的是，我们可以用递归回溯。
所以，方法一如下：

方法一：暴力递归

暴力递归就要想到递归三部曲：

递归函数的设计和功能：back_track(n); 含义是：求长度为n的数，最后分段后的最大乘积，这里我们不需要关心分成多少段
递归函数的终止条件: 如果n <= 4, 显然back_track(n) = n，初始条件也就是我们不用计算就能得到的。
下一步递归：对于长度n，我们需要减少递归参数n，如果第一段为1，显然下一步递归为back_track(n-1),如果第一段为2，则下一步递归为
back_track(n-2)…因为要至少分2段，所以，最后一次可能的情况为最后一段为n-1, 下一步递归为back_track(1)，因此，每一步可能的结果为
1 * back_track(n-1), 2 * back_track(n-2), …, (n-1) * back_track(1),在n-1种情况中取一个最大值即可。这里我们不用关系back_track(n-1)等的值为多少，因为最终会递归到我们的终止条件，因此绝对是可以求出来。

于是，有了上面三部曲，递归代码如下：

class Solution {
public:
    int back_track(int n) {
        // n <= 4, 表明不分，长度是最大的
        if (n <= 4) {
            return n;
        }

        int ret = 0;
        for (int i = 1; i < n; ++i) {
            ret = max(ret, i * back_track(n - i));
        }
        return ret;
    }
    int cutRope(int number) {
        // number = 2 和 3 时，分 2 段和分 1 段的结果是不一样的，所以需要特判一下
        if (number == 2) {
            return 1;
        }
        else if (number == 3) {
            return 2;
        }
        return back_track(number);
    }
};

时间复杂度：O(n!)
空间复杂度：O(n), 最多分n段，每段长度为1，所以递归深度为n

方法二：记忆化递归

根据方法一，假设求back_track(7)，如下图：

我用f() 替代 back_track(),可知，红色的部分重复了。
因此，我们可以开一个数组，把计算过的结果存起来。
步骤如下：

初始化一个大小为 n+1 的数组，初始值为 -1 ，也可以-2，反正是不可能得到的值

在方法一的代码上，记录一下，详细代码如下
代码如下：

class Solution {
public:
  int back_track(int n, vector<int> &mark) {
      if (n <= 4) {
          return n;
      }
      // 在方法一的基础上添加
      if (mark[n] != -1) {
          return mark[n];
      }

      int ret = 0;
      for (int i = 1; i < n; ++i) {
          ret = max(ret, i * back_track(n - i));
      }
      // 添加部分
      return mark[n] = ret;
  }
  int cutRope(int number) {
      if (number == 2) {
          return 1;
      }
      else if (number == 3) {
          return 2;
      }
      // 添加部分
      vector<int> mark(number, -1);
      return back_track(numberm, mark);
  }
};

时间复杂度：O(n^2)
空间复杂度：O(n)

方法三：动态规划

有的书上认为方法二是一种递归版本的动态规划。
所以，我们可以将方法二修改为迭代版本的动态规划。

代码如下：

class Solution {
public:
    int cutRope(int number) {
        if (number == 2) {
            return 1;
        }
        else if (number == 3) {
            return 2;
        }

        vector<int> f(number + 1, -1);
        for (int i = 1; i <= 4; ++i) {
            f[i] = i;
        }
        for (int i = 5; i <= number; ++i) {
            for (int j = 1; j < i; ++j) {
                f[i] = max(f[i], j * f[i - j]);
            }
        }
        return f[number];
    }
};

时间复杂度：O(n^2)
空间复杂度：O(n)

总的来说，方法一是基础。方法二，方法三都是在方法一的基础上修改的。

Q:接下来，我们就可以开篇的问题了，什么样的题适合用动态规划？
A：一般，动态规划有以下几种分类：

最值型动态规划，比如求最大，最小值是多少
计数型动态规划，比如换硬币，有多少种换法
坐标型动态规划，比如在m*n矩阵求最值型，计数型，一般是二维矩阵
区间型动态规划，比如在区间中求最值

其实，根据此题的启发，我们可以换种想法，就是什么样的题适合用暴力递归？
显然就是，可能的情况很多，需要枚举所有种情况。只不过动态规划，只记录子结构中最优的解。