【数学知识】剑指 Offer 14- I. 剪绳子-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月16日下午7:38

发现数学规律。动态规划也能做。

class Solution {
    public int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        int res = n / 3;
        int mod = n % 3;
        if(mod == 0){
            return pow(3, res);
        }else if(mod == 1){
            return pow(3, res - 1) * 4;
        }else{
            return pow(3, res) * 2;
        }

    }
    public int pow(int a, int b){
        int sum = 1;
        int t = a;
        while(b != 0){
            if((b & 1) == 1){
                sum *= t;
            }
            b = b >> 1;
            t *= t;
        }
        return sum;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月10日下午4:31

def cuttingRope(n):
    # 2、3为特殊情况
    if n == 2:
        return 1
    if n == 3:
        return 2

    res = n // 3
    mod = n % 3
    if mod == 0:
        return pow(3,res)
    if mod == 1:
        # 如果余数是1，将1和一个3凑成一个4
        return pow(3,res-1) * 4
    if mod == 2:
        return pow(3,res) * 2

0 赞同 0 条回复

lucca 普通 2023年1月9日上午10:48

DP不咋会，看了题解

class Solution {
    public int cuttingRope(int n) {
        int[] f = new int[n+1];
        f[2] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                f[i] = Math.max(
                    f[i], Math.max(j * (i-j), f[j] * (i-j))
                );
            }
        }
        return f[n];
    }
}

数学也不咋会


class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) return n-1;
        int a = n / 3, b = n % 3;
        if (b == 0) return (int) Math.pow(3, a);
        if (b == 1) return (int) Math.pow(3, a - 1) * 4;
        return (int) Math.pow(3, a) * 2;
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月2日下午4:34

func cuttingRope(n int) int {
    //动态规划
    dp := make([]int, n + 1) //动态数组
    for i := 2; i <= n; i++ {
        for j := 1; j < i; j++ {
        // j * (i - j):i-j不在拆分 j * dp[i - j] :将i-j继续拆分
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])) 
        }
    }
    return dp[n]
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

0 赞同 0 条回复

🚲南下普通 2022年12月2日下午1:58

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n+1);
        for(int i = 2; i <= n;i++){//i<=n，动态规划
            int curmax = 0;
            for(int j = 1; j < i; j++){
                int tempmax = max((i-j)*j, j*dp[i-j]);
                curmax = max(curmax,tempmax); //转移方程
            }
            dp[i] = curmax;
        }
        return dp[n];
    }
};

0 赞同 0 条回复

xye 普通 2022年11月25日下午7:25

func cuttingRope(n int) int {
    if n < 4 {
        return n - 1
    }
    res := 1
    for n > 4 {
        res *= 3
        n -= 3
    }
    return res * n
}

时间O(n) 空间O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年11月21日上午8:36

时间：O(1)
空间：O(1)

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 推理判断：当绳子长度大于3时，需要尽量把绳子切分成差不多一样的长度，且不能同时存在2和4的长度，2+4=3+3
        # 特殊情况
        if n == 2:
            return 1
        if n == 3:
            return 2
        # 绳子长度除3取整表示可以切分成这么多段的3，余数为1时可以合并一个3，余数为2时保持不变
        res = n // 3
        mod = n % 3
        if mod == 0:
            return 3 ** res
        elif mod == 1:
            return 3 ** (res - 1) * 4
        else:
            return 3 ** res * 2

0 赞同 0 条回复

lobort 普通 2022年11月16日下午8:15

class Solution {
     //记得推论因数3要比较多 余数为1的时候 分为2×2
    public int cuttingRope(int n) {
        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }
        if(n > 3){
            int count  = n / 3;
            int mode   = n % 3;
            if(mode == 2){
                return (int)Math.pow(3, count)* mode;
            }
            if(mode == 1){
                return  (int)Math.pow(3, count-1)*4;
            }
            return (int)Math.pow(3,count);
        }
        return -1;
    }
}class Solution {
    public int cuttingRope(int n) {
        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }
        if(n > 3){
            int count  = n / 3;
            int mode   = n % 3;
            if(mode == 2){
                return (int)Math.pow(3, count)* mode;
            }
            if(mode == 1){
                return  (int)Math.pow(3, count-1)*4;
            }
            return (int)Math.pow(3,count);
        }
        return -1;
    }
}

0 赞同 0 条回复

小肸永久会员 2022年11月16日下午3:45

思路一：动态规划。对于长度为2的绳子，只能剪成1，1两段；对于长度为3的绳子，剪成1，2两段乘积最大，因为(11)1<2*1。时间复杂度O(N^2)，空间复杂度O(1)。

class Solution {
    public int cuttingRope(int n) {
        if (n <= 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        // dp[i]表示长度为i的绳子剪成m段后的各段绳子乘积的最大值（i>=4）
        int[] dp = new int[n + 1];
        // dp数组初始化
        dp[1] =1;
        dp[2] = 2;
        dp[3] = 3;
        int max = 0;
        for (int i = 4; i <= n; i ++) {
            max = 0;
            // 为什么是i/2，因为举个列子，n=4,dp[1]*dp[3]=dp[3]*dp[1]。
            for (int j = 1; j <= i / 2; j ++) {
                int temp = dp[j] * dp[i - j];
                if (max < temp) {
                    max = temp;
                }
                dp[i] = max;
            }
        }
        return dp[n];
    }
}

思路二：动态规划。对于长度为i的绳子，两种情况，一种情况是剪去长度为j的绳子剩下长度为i-j的绳子（不继续剪），另一种情况是剪去长度为j的绳子剩下长度为i-j的绳子（继续剪）。时间复杂度O(N^2)，空间复杂度O(1)。

class Solution {
    public int cuttingRope(int n) {
        if (n <= 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        // dp[i]表示长度为i的绳子剪成m段后的各段绳子乘积的最大值（i>=4）
        int[] dp = new int[n + 1];
        // dp数组初始化
        dp[2] = 1;
        for (int i = 3; i <= n; i ++) {
            for (int j = 1; j < i; j ++) {
                // 这里为什么算上dp[i]，因为还需要和前几次j取值后的dp[i]做比较
                dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
            }
        }
        return dp[n];
    }
}

思路三：数学知识。n>=5时尽可能把绳子剪成3的绳子段，当n4时剪成22，因为22>1*3。时间复杂度O(1)，空间复杂度O(1)。

class Solution {
    public int cuttingRope(int n) {
        if (n <= 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int threeCount = n / 3;
        // 说明此时剪成2*2比较好，因为2*2>3*1
        if (n - threeCount * 3 == 1) {
            threeCount --;
        }
        int twoCount = (n - threeCount * 3) / 2;
        return (int)(Math.pow(3, threeCount) * Math.pow(2, twoCount));
    }
}

0 赞同 0 条回复

@ 普通 2022年11月16日上午11:29

思路：数学推导可以得出：尽可能将绳子以长度 333 等分为多段时，乘积最大

算法流程：

(1)当 n≤3 时，按照规则应不切分，但由于题目要求必须剪成 m>1 段，因此必须剪出一段长度为 1的绳子，即返回 n−1 。
(2)当 n>3 时，求 n 除以3的整数部分a和余数部分b （即 n=3a+b），并分为以下三种情况：

当 b=0 时，直接返回 3^a;
当 b=1时，要将一个 1+3 转换为 2+2，因此返回 3^a−1 * 4;
当 b=2 时，返回 3^a * 2;

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年11月15日下午7:43

dp:
注意： dp[i]的转移方程为dp[i] = max(dp[i], max(j * (i – j), j * dp[i – j]))

class Solution {
    public int cuttingRope(int n) {
      int [] dp = new int[n+1];
      dp[2] = 1;
      for (int i = 3;i < n+1;i++){
          for(int j = 2;j<i;j++){
              dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
          }
      }
      return dp[n];
    }
}

class Solution {
    public int cuttingRope(int n) {
    //   int [] dp = new int[n+1];
    //   dp[2] = 1;
    //   for (int i = 3;i < n+1;i++){
    //       for(int j = 2;j<i;j++){
    //           dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
    //       }
    //   }
    //   return dp[n];
    if (n <=2){
        return 1;
    }
    if (n == 3){
        return 2;
    }
    int res = n/3;
    int mod = n%3;
    if (mod == 0){
        return pow(3,res);
    }else if (mod == 1){
        return pow(3,res-1)*4;
    }else{
        return pow(3,res)*2;
    }

    }
    int pow (int a,int n){
        int sum = 1;
        for (int i = 1;i <=n;i++){
            sum = sum*a;
        }
        return sum;
    }
}

0 赞同 0 条回复

y 普通 2022年11月15日下午5:24

var cuttingRope = function(n) {
  const dp =new Array(n + 1).fill(0);
  dp[2] = 1;
  for (let i = 3; i <= n; i++) {
      for (let j = 1; j < i - 1; j++) {
          dp[i] = Math.max(dp[i], j * (i - j), dp[i - j] * j)
      }
  }
 return dp[n];
};

时间：O(n^2^)
空间：O(n)

0 赞同 0 条回复

波波_1936 普通 2022年11月14日下午5:40

    /**
     * 剑指 Offer 14- I. 剪绳子
     */
    public int cuttingRope1(int n) {
        //时间复杂度O(n^2)
        //空间复杂度O(n)
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            //j遍历到小于i的值
            for (int j = 1; j < i - 1; j++) {
                //dp[i]表示将长度为i的绳子剪成至少2段绳子之后，这些绳子长度的最大乘积
                dp[i] = Math.max(dp[i], Math.max((j * (i - j)), (j * dp[i - j])));
            }
        }
        return dp[n];
    }

0 赞同 0 条回复

T 普通 2022年11月14日下午4:58

class Solution {
    // 动态规划
    public int cuttingRope(int n) {
        // dp[i]表示，i长度的绳子最大乘积是多少
        int[] dp = new int[n + 1];
        dp[2] = 1;
        // i表示绳子长度
        for(int i = 3; i <= n; i++) {
            // 将当前i长度的绳子分成 j 和 i - j两段
            for(int j = 2; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年11月14日上午10:54

动态规划

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i < n + 1; i++){
            for(int j = 2; j < i; j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月13日上午11:26

求次方采用快速幂时间复杂度为O（lgn），空间复杂度为O（1）.

class Solution {
    public int cuttingRope(int n) {
         if(n <= 2) return 1;
         if(n == 3) return 2;
         int res = n / 3;
         int k = n % 3;
         if(k == 0){
             return (int)Math.pow(3,res);
         }else if(k == 1){
             return (int)Math.pow(3,res - 1)*4;
         }else{
             return (int)Math.pow(3,res)*k;
         }
    }
}
//快速幂方式
class Solution {
    public int cuttingRope(int n) {
         if(n <= 2) return 1;
         if(n == 3) return 2;
         int res = n / 3;
         int k = n % 3;
         if(k == 0){
             return pow(3,res);
         }else if(k == 1){
             return pow(3,res - 1)*4;
         }else{
             return pow(3,res)*k;
         }
    }
    int pow(int m,int n){
        int sum = 1;
        while(n != 0){
            if(n % 2 == 1){
                sum = sum * m;
            }
            m = m * m; 
            n = n >> 1;
        }
        return sum;
    }
}

0 赞同 0 条回复

大宝子冲永久会员 2022年11月12日下午4:49

class Solution {
    public int cuttingRope(int n) {
        if(n<=2) return 1;
        if(n == 3) return 2;
        int res = n/3;
        int mod =n%3;
        if(mod == 0) return  (int)Math.pow(3,res);
        if(mod == 1) return  (int)Math.pow(3,res-1)*4;
        else{
           return  (int)Math.pow(3,res)*2;  
        } 
    }
}

时间空间复杂度O（n)

0 赞同 0 条回复

天然普通 2022年11月12日下午3:20

时间/空间 O(1)

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n<=3:return n-1
        sum =1
        while n>4:
            sum *=3
            n -=3
        return sum*n

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n<4:return n-1
        k,m = n//3,n%3
        if m==0: return 3**k
        elif m==1:return 3**(k-1)*4
        else: return 3**k*2

0 赞同 0 条回复

派大星普通 2022年11月12日下午12:01

class Solution {
//时间复杂度O(n)
//空间复杂度O(n)
    public int cuttingRope(int n) {
        int tem = 0;
        for (int i = 2; i <= n; i++) {
            if(multply(n,i) > tem){
                tem = multply(n,i);
            }
        }

        return tem;

    }
    public int function(int n,int i){
        int sum = 1;
        int tem = 1;
        while(tem != 0){
            if((i & tem) != 0) sum *= n;
            tem <<= 1;
            n *= n;
        }
        return sum;
    }
    public int multply(int n,int i){
        int a = n / i;
        int b = n % i;
        if(b > 0){
            return function(a+1,b) * function(a,i - b);
        }else{
            return function(a,i);
        }
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月11日下午11:46

动规

/**
dp[i] 表示长度为i的绳子剪出来的最大值
 */
class Solution {
    public int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n + 1];
        //因为m>1 dp[2]初始化为1
        dp[2] = 1;
        dp[3] = 2;
        //2,3为特殊情况
        //i表示绳子长度
        for(int i = 4;i <= n;i++){
            //i - j >= 2 ，j表示第一次剪掉的长度
            //此时有两种选择
            //1.减去j，不再减 剩下的长度为i-j
            //2.减去j，继续减 最大长度为dp[i-j]
            for(int j = 1;j <= i - 2;j++){
                dp[i] = Math.max(Math.max(dp[i-j],i-j)*j,dp[i]);
            }
        }
        return dp[n];
    }
}

数论

/**
数论
最优： 3 。把绳子尽可能切为多个长度为 3的片段，留下的最后一段绳子的长度可能为 0,1,2三种情况。
次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1 。若最后一段绳子长度为 1；则应把一份 3 + 1 替换为 2 + 2，因为2×2>3×1。
 */
class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int sum = 1;
        while(n > 4){
            sum *= 3;
            n -= 3;
            //当n小于等于4时 有三种情况
            //4->2*2 3 -> 3 2 -> 2不影响最终结果 
        }
        return sum * n;
    }
}

/**
数论
最优： 3 。把绳子尽可能切为多个长度为 3的片段，留下的最后一段绳子的长度可能为 0,1,2三种情况。
次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1 。若最后一段绳子长度为 1；则应把一份 3 + 1 替换为 2 + 2，因为2×2>3×1。
 */
class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int r = n % 3;
        int l = n / 3;
        if(r == 0){
            return (int)Math.pow(3,l);//全是3 都变成3
        }else if(r == 1){
            //剩下3+1 乘以4
            return (int)Math.pow(3,l-1) * 4;
        }else if(r == 2){
            return (int)Math.pow(3,l) * 2;//剩余2
        }
        return 0;
    }
}

0 赞同 0 条回复

黎昕普通 2022年11月11日下午5:50

通过高数知识直接化简得到结果输出即可
时间/空间 O(1)

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 通过数学方法完全证明得到结果，时间从 O（n）降到O（1）
        if n<4:
            return n-1
        m=n//3
        q=n%3
        if q==0:
            return 3**m
        elif q==1:
            return 3**(m-1)*4
        else:
            return 3**m*2

0 赞同 0 条回复

是梦终空永久会员 2022年11月11日下午3:41

时间O(logn)
空间O(1)

class Solution {
    public int cuttingRope(int n) {
        // 先判断特殊情况，等于2,3就不用再分了
        if(n <=2)   return 1;
        if(n == 3)  return 2;
        //尽可能的把绳子分割成长度为3的子绳子，因为5以上包括5就得开始分割，2*4<=3*3.
        //先求出能有多少个3
        int res = n/3;
        // 给3取余，得到余数
        int mod = n%3;
        int sum = 0;
        // 等于0就直接返回就行
        if(mod==0){
            sum = F(3,res);
        //等于1 就取出一个3，让它和余数3组成4，可使结果更大
        }else if(mod == 1){
            sum = F(3,res-1)*4;
            // 等于2 直接与结果相乘
        }else
            sum = F(3,res) * 2;
        return sum;
    }
    // n的res次方
    public int F(int n,int res){
        int sum = 1;
        for(int i = 1;i<=res;i++){
            sum*=n;
        }
        return sum;
    }
}

0 赞同 0 条回复

庄重普通 2022年11月11日下午2:53

// 思路：
//     1.最大限度第把每段分为3，并且仅存一个2或者4的时候，所有的乘积最大
class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 2)
            return 1;
        if(n == 3)
            return 2;

        int res = n / 3;
        int mod = n % 3;

        if(mod == 0)
            return pow(3,res);
        else if(mod == 1)
            return pow(3,res-1) * 4;
        else//mod == 2
            return pow(3,res) * 2;

    }
};
//时间复杂度O(1)
//空间复杂度O(1)

0 赞同 0 条回复

just 普通 2022年11月11日下午12:47

//dp动态规划
class Solution {
public:
int integerBreak(int n) {
int dp[n+1];
for(int i=0;i<n+1;++i) dp[i]=0;
dp[2]=1;
for(int i=3;i<=n;++i){
for(int j=1;j<=i-2;++j){
dp[i]=max(dp[i],max(j(i-j),jdp[i-j]));
}
//dp[i]=max(dp[i],i-1);
}
return dp[n];
}
};

0 赞同 0 条回复

So 普通 2022年11月11日上午8:49

class Solution {
    public int cuttingRope(int n) {
        if (n <= 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int res = n / 3;
        int mod = n % 3;
        if (mod == 0) {
            return pow(3, res);
        } else if (mod == 1) {
            return pow(3, res - 1) * 4;
        } else {
            return pow(3, res) * 2;
        }
    }
    public int pow(int m, int n) {
        int res = 1;
        for (int i = 0; i < n; i++) {
            res *= m;
        }
        return res;
    }
}

时间：O(1)，空间：O(1)

0 赞同 0 条回复

青木普通 2022年11月11日上午12:02

/**
    纯靠猜，没有证明，找出最多的3就行，乘1没用，不考虑1（数学证明好难T_T）

    时间O(1)
    空间O(1)
 */

class Solution {
    public int cuttingRope(int n) {
        if(n<3) return 1;
        if(n==3) return 2;
        if(n==4) return 4;
        int yu = n % 3;
        int k = n/3;
        if(yu==1){
            yu = 4;
            k -= 1;
        }
        if(yu==0){
            yu = 1;
        }
        return (int)Math.pow(3, k) * yu;
    }
}

/**
    无优化的dp，感觉好懂一点，i表示输入的数字，
    j表示拆分的值， dp[i]就表示j的右边不拆和拆了之后的极大值

    时间O(n^2)
    空间O(n)
 */

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        int curMax = 0;
        for(int i=2; i<=n; i++){
            for(int j=1; j<i; j++){
                curMax = Math.max(curMax, Math.max(j*(i-j), j*dp[i-j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}

0 赞同 0 条回复

【数学知识】剑指 Offer 14- I. 剪绳子

共以下 26 个回答

DP不咋会，看了题解

数学也不咋会

# 回答此问题取消回复

【数学知识】剑指 Offer 14- I. 剪绳子

共以下 26 个回答

DP不咋会，看了题解

数学也不咋会

# 回答此问题 取消回复

# 回答此问题取消回复