剪绳子

python解法：动态规划
带备忘录的动态规划： :

    def cutRope(self, number):
        # write code here
        if number == 0:
            return 0
        elif number in (1,2):
            return 1
        elif number == 3:
            return 2
        return self.subFunction(number)

    def subFunction(self, number):
        tempL = [0]*(number+1)
        tempL[0] = 1
        maxV = 0
        if tempL[number] != 0:
            return tempL[number]
        for i in range(1, number+1):
            ans = i*self.subFunction(number-i)
            if ans>maxV:
                maxV = ans
                tempL[number] = maxV
        return maxV 

class Solution {
public:
  // Dynamic Programming (Bottom-Up)
  int cutRope(int number) {
    vector<int> dp(number + 1);
    dp[1] = dp[2] = 1;
    
    for (int i = 3; i <= number; ++i)
      for (int j = 1; j <= i - 1; ++j)
        // 状态转移方程
        dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
    
    return dp.back();
  }

  // 解法2 -- 记忆化递归 (Top-Down)
  int cutRopeII(int number) {
    memo_.resize(number + 1);
    return cut(number);
  }
  
private:
  vector<int> memo_;
  
  int cut(int n) {
    if (n <= 2)
      return 1;
    
    if (memo_[n] > 0)
      return memo_[n];
    
    int ans = 1;
    for (int i = 1; i <= n - 1; ++i)
      ans = max(ans, max(i * (n - i), i * cut(n - i)));
    
    return memo_[n] = ans;
  }
  
};

class Solution {
public:
    int cutRope(int number) {
        if(number < 2)
            return 0;
        if(number == 2)
            return 1;
        if(number == 3)
            return 2;
        vector<int> res(number + 1, 0);
        res[1] = 1;
        res[2] = 2;
        res[3] = 3;
        int max_length = 0;
        for(int i = 4; i <= number; ++i)
        {
            for(int j = 1; j <= i / 2; ++j)
            {
                if(res[i - j] * j > max_length)
                    max_length = res[i -j] * j;
            }
            res[i] = max_length;
            max_length = 0;
        }
        return res[number];
    }
};

class Solution {
public:
    int cutRope(int number) {
        vector<int>dp(number+1,1);
        for(int i=1;i<=number;i++){
            for(int j=1;j<=i;j++){
                dp[i]=max(dp[i],dp[i-j]*j);
            }
        }
        return dp[number];
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        // 贪心，时间复杂度O(N)，空间复杂度O(1)
        if (n < 4) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
};

class Solution:
    def cutRope(self , number: int) -> int:
        # write code here
        l=[]
        for i in range(2,number+1):
            x=number//i
            lf=number-x*i
            res=x**(i-lf)*(x+1)**lf
            l.append(res)
        return max(l)

// 解法采用，多3少2无1的方法 class Solution {
public:
    int cutRope(int number) {
        int a = number / 3;
        int b = 0;
        if(number % 3 ) b = number % 3;
        int ret = 0;
        if(b == 1) ret = pow(3, a-1)* 4;
        else ret = b > 0 ? pow(3, a) * b : pow(3, a);
        
        return ret;
    }
        
        
}; 

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

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

    public int cutRope(int target) {
        if(target < 3){
            return target - 1;
        }
        
        int res = 1 ;
        while( target > 4){
            res *= 3;
            target -= 3;
        }
        return target * res;
    }

import java.util.*;
public class Solution {
    public int cutRope(int target) {
        //找规律：三种情况
        // 5 = 3*2；  3^(5/3)*2;
        // 6 = 3*3;   3^(6/3);
        // 7 = 3*2*2;  3^(7/3-1)*2;
         if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        if(target==4){
            return 4;
        }
        int index = (target-5) % 3;
        if(index == 0)return (int)Math.pow(3,target/3)*2;
        if(index == 1)return (int)Math.pow(3,target/3);
        return (int)Math.pow(3,target/3-1)*4;
       
    }
    
 
}

function cutRope(number)
{
    // write code here
    var arr = [2,3,4,6,9,12];
    var a = Math.floor((number - 2) / 6);
    var b = number - a * 6 - 2;
    if(a == 0){
        return arr[b];
    }
    var sum = arr[b];
    for(var i = 0;i < a;i++){
        sum *= 9;
    }
    return sum;
}

思路

首先，根据中学知识就能知道，尽可能分成等长的时候乘积最大。

中学时有这种题:
把长为a的线段分成两段，问两段的长度分别是多少时，才能使得以这两段分别作为长、宽所得到的矩形面积最大？
结论是对半分时最大。记得当时老师类推过分成m份，也是等分时乘积最大。
也就是求f(x)=(x)^(n/x)的最大值。

高数学的导数指数什么的忘了挺多，但可以笨办法算：
等分后要么都是2，要么都是3（4以上可以继续分），随便找个数n=6，就知道分成3更大。
接下来尽可能分成3即可。

代码

    public int cutRope(int target) {
        int res = 1;
        for (int i = target / 3; i > 0; i--) res *= 3;
        if (target % 3 == 2) res *= 2;
        if (target % 3 == 1) res = res / 3 * 4;
        return res;
    }