JZ67 题解 | #剪绳子#

题意分析

• 题目的意思是给出一个数字，让我们将这个数字进行分解，然后找到分解后所有的数的乘积最大的情况。
• 样例分析，我们可以将8分解为2x3x3，得到的结果就是18,这个可以自己暴力枚举一下所有的情况进行验证。

思路分析

• 这个题目，我主要用的是三种方法进行解答

解法一 暴力枚举

• 我们可以发现，我们进行从小到大的枚举，当我们进行求解某一个数字的时候，我们已经求出了之前的所有的数的最优的情况，那么我们可以枚举将这个数字x分解出1,2,...x-1的所有的情况，然后维护最大的值就行了。
• 代码如下
  • 开了双重for循环，时间复杂度为O(n^2)
  • 开了数组存储每个状态的最优解，空间复杂度为O(n)

    class Solution {
    public:
    int f[100]; // 用来维护当前所有的数字的最优解的值
    int cutRope(int number) {
      // 处理特殊的情况
      if(number<=3){
          return number-1;
      }
      for(int i=2;i<=number;i++){
          if(i<=3){
              f[i]=i;
          }
          // 暴力枚举将这个数字分解出j后的情况，维护最大的值
          for(int j=1;j<i;j++){
              f[i]=max(f[i],f[j]*(i-j));
          }
      }
      return f[number];
    }
    };

解法二 递归求解

• 我们可以发现，当我们求某一个数字的时候，我们只需要将这个数字分解出一个1,2,3。对于3以上的数字，其实可以分解成这三个数字，比如4=2x2,5=2x3。对于分解出1的情况，我们发现这个是对答案没有贡献的。所以直接忽略。我们只需要讨论2和3的情况。所以，我们只需要将数字分为2和3组成的就行了。

• 如下图
  

• 代码如下，

  • 需要对每个状态进行求解，时间复杂度为O(n)
  • 只开了几个变量进行存储,空间复杂度为O(1)

    class Solution {
    public:
    int dp(int x){
      // 递归出口
      if(x<=3){
          return x;
      }
      // 将数字划分出一个2或者3维护最大的值即可
      return max(dp(x-2)*2,dp(x-3)*3);
    }
    int cutRope(int number) {
      return dp(number);
    }
    };

解法三 找规律

• 我们发现，最优的解一定是将这个数字尽量平均分为若干份进行求解。我们假设我们存在一个数字为x，我们将这个数字平均分为尽量m等份，那么每一份就是x/m(假设可以等分），乘积就是,我们令x/m=y，那么就是y^m,我们从这里面抽取出两份y，加入我们把这两份不进行均分，那么就是(y-1),(y+1)，我们发现，其结果肯定是比y^2小的。依次类推，我们可以得到结论，尽量将这个数字均分成若干等份就是最优的答案。所以我们可以枚举分成的份数。对于不能均分的情况，我们就把多余的尽量给每份分一个。
• 代码如下
  • 从1-number进行遍历，时间复杂度O(n)
  • 只开了少数几个变量存储，空间复杂度为O(1)

    class Solution {
    public:
    int cutRope(int number) {
      int ans=0;
      // 枚举分成的份数多少
      for(int i=1;i<=number;i++){
          int pre=number/i;
          int more=number%i;
          int res=1;
          for(int j=1;j<=more;j++){
              res=res*(pre+1);
          }
          // 对于余数，我们就给余数份多分一个就行
          for(int j=more+1;j<=i;j++){
              res=res*pre;
          }
          ans=max(ans,res);
      }
      return ans;
    }
    };