剪绳子

http://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8

描述

这是一篇针对初学者的题解，从暴力递归到动态规划一步步讲解。
知识点：递归，动态规划
难度：二星

题解

题目描述：给定一个长度为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 &lt;= 4, 表明不分，长度是最大的
        if (n &lt;= 4) {
            return n;
        }

        int ret = 0;
        for (int i = 1; i &lt; 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)，如下图：
![图片说明](https://uploadfiles.nowcoder.com/images/20200523/284295_1590216999783_2CC2B62A31846CE8FC9AB8E71A5EB53D "图片标题")
我用f() 替代 back_track(),可知，红色的部分重复了。
因此，我们可以开一个数组，把计算过的结果存起来。
步骤如下：

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

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

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

      int ret = 0;
      for (int i = 1; i &lt; 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&lt;int&gt; 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&lt;int&gt; f(number + 1, -1);
        for (int i = 1; i &lt;= 4; ++i) {
            f[i] = i;
        }
        for (int i = 5; i &lt;= number; ++i) {
            for (int j = 1; j &lt; i; ++j) {
                f[i] = max(f[i], j * f[i - j]);
            }
        }
        return f[number];
    }
};

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

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

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