九号球普通 2023年11月21日下午10:40

“`java
//大于等于4的都可以拆分成2*(x-2)，而3个2又可以转为2个3，所以就是先截3
class Solution {
public int cuttingBamboo(int bamboo_len) {
if (bamboo_len <= 3) { return bamboo_len - 1; } int quoient = bamboo_len/3; int remainder = bamboo_len%3; if (remainder == 1) { return (int)Math.pow(3, quoient - 1) * 4; } else if (remainder == 2){ return (int)Math.pow(3, quoient) * remainder; } else { return (int)Math.pow(3, quoient); } } }

0 赞同 0 条回复

招舟子普通 2023年9月2日下午3:47

class Solution {
public int cuttingRope(int n) {
if(n<=2){
return 1;
}
if(n3){
return 2;
}
int res = n/3;
int mod = n%3;
if(mod0){
return pow(3,res);
}
if(mod1){
return pow(3,res-1)4;
}
if(mod2){
return pow(3,res)2;
}
return 0;
}
public int pow(int a,int b){
int sum = 1;
for(int i=0;i<b;i++){
sum= sum*a;
}
return sum;
}
}
使用数学规律

0 赞同 0 条回复

彦，，# 普通 2023年8月5日下午3:11

动态规划
int cuttingRope(int n) {
        vector <int> dp(n+1);
        for(int i =2;i <=n; i++)
        {
            int curMax = 0;
            for(int j=1; j<i; j++)
            {
                curMax = max(curMax, max(j * (i-j) , j*dp[i - j]));
            }
            dp[i] = curMax;
    }
    return dp[n];
    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:26

“`C++
int cuttingRope(int n) {
vector dp(n + 1, 0);
dp[2] = 1; // 初始化，当绳子长度为 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), dp[j] * (i - j)));
    }
}

return dp[n];

}

“`

0 赞同 0 条回复

憨憨永久会员 2023年7月18日下午1:27

数学分析

class Solution {
    public int cuttingRope(int n) {
        if(n <= 2)return 1;
        if(n == 3)return 2;
        if(n == 4)return 4;

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

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月16日下午8:16

动态规划

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

0 赞同 0 条回复

屠龙手段普通 2023年7月16日下午6:29

动态规划时间复杂度O(n^2) 空间复杂度O(n)

class Solution(object):
    def cuttingRope(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]

0 赞同 0 条回复

mpweixin用户普通 2023年7月16日上午9:09

java
class Solution {
    public int cuttingRope(int n) {
        /*
            分成等分的话乘积最大，1,2,3,4不可再拆分，拆分段长度为3是最优的，对3取模后余数为0或1或2,1            加到3里面形成4,2直接相乘
        */
        if(n <= 2) {
            return 1;
        }
        if(n == 3) {
            return 2;
        }

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

        if(mod == 0) {
            res = (int)Math.pow(3, res);
        } else if(mod == 1) {
            res = (int)Math.pow(3, res - 1) * 4;
        } else {
            res = (int)Math.pow(3, res) * 2;
        }
        return res;
    }
}

时间复杂度和空间复杂度都为o(1)

0 赞同 0 条回复

BOZ 普通 2023年7月15日下午12:18

【思路】将n拆解为3和2的组合
【复杂度】时间空间均为O(1)

class Solution {
public:
    int cuttingRope(int n) {
        if (n < 4) return n - 1;

        int mod = n % 3;
        if (mod == 1) return std::pow(3, n / 3 - 1) * 4;
        else if (mod == 2) return std::pow(3, n / 3) * 2;
        else return std::pow(3, n / 3);
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月14日下午9:20

想不出来，看官解的
时间：O(1)
空间：O(1)

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

0 赞同 0 条回复

江畅普通 2023年7月13日上午10:25

// 剪绳子
// 时间复杂度 O(N^2)
// 空间复杂度 O(N)
class Solution {
public:
    int cuttingRope(int n) {

        // dp[n] 为所求结果
        // dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
        vector<int> dp(n + 1);  // 初始化为 0

        // 1 * (2 - 1) = 1
        dp[2] = 1;

        for (int i = 3; i <= n ; ++i) {
            for (int j = 1; j < i - 1; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月10日下午5:31

MY

帅弟

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;
        }
        return 0;
    }
};

0 赞同 0 条回复

WhyNot 普通 2023年7月9日下午11:15

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){//要与其中一个3构成4
     return pow(3,res-1)*4;
 }
 else
 { //除完余2，可单独乘
     return pow(3,res)*2;
 }
}

时间复杂度是O(1)
空间复杂度是O(1)

0 赞同 0 条回复

Jerry 普通 2023年7月9日下午10:45

 // dp
class Solution {
    int[] memo; // 备忘录

    public int cuttingRope(int n) {
        memo = new int[n + 1];
        return dp(n);
    }

    int dp(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (memo[n] > 0) return memo[n];


        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            int compareRes = i * Math.max(dp(n - i), n - i); // dp func
            res = Math.max(res, compareRes);
        }
        memo[n] = res;
        return res;
    }
}

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

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月9日下午10:13

时间复杂度：O(logN)
空间复杂度：O(1)

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 x, int n){
        int sum = 1;
        while(n != 0){
            if((n & 1) == 1){
                sum *= x;
            }
            x = x*x;
            n = n >>1;
        }

        return sum;
    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月9日下午12:06

直接看答案系列。

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 条回复

Ming 普通 2023年7月9日上午12:06

n由3组成，则乘积是最大的，则n是三的倍数余0余1余2的情况

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

0 赞同 0 条回复

行动派小彩笔普通 2023年7月8日下午10:45

//时间o(1),空间O(1)
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=2) return 1;
        else 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;

    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月8日下午10:30

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1

        for i in range(3, n + 1):
            for j in range(1, i // 2 + 1):
                dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j))

        return dp[n]

动规标准解法

0 赞同 0 条回复

局外人普通 2023年7月8日下午10:26

思路：动态规划——dp[i]代表长度为i时的最大剪绳乘积；状态转移方程：将i分为j与i-j，若i-j不继续分割，则结果为j(i-j); 若i-j继续分割，则结果为jdp[i-j]
时间复杂度：O(n²) 空间复杂度:O(n)

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];

        for(int i=2; i<=n; i++){
            int curMax = 0;
            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 条回复

mpweixin用户永久会员 2023年7月8日下午8:32

//思路：尽量减出“3”，讨论一下最后一段不是3的情况
//时间O(logn) 空间O(1)
public int cuttingRope(int n) {
        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }

        int count = n / 3;  //  能分成几个3
        int remainder = n % 3;

        if(remainder == 0){
            return pow(3,count);
        }
        if(remainder == 1){
            //凑成四
            return pow(3,count - 1) * 4;
        }

        return pow(3,count) * 2;   
    }

    public int pow(int n, int m){

        int weight = n;
        int result = 1;

        while(m != 0){
            result = (m & 1) == 1? result * weight : result;

            weight = weight * weight;
            m = m >> 1;
        }

        return result;

    }

0 赞同 0 条回复

张开怀普通 2023年7月8日下午8:22

“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;
}
}
int pow(int a, int n){
int sum =1;
for(int i=1; i<=n; i++){
sum =sum * a;
}
return sum;
}
};
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

伏月三十普通 2023年7月8日下午5:44

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);
        }else if(mod==1){
            return (int)Math.pow(3,res-1)*4;
        }else{
            return (int)Math.pow(3,res)*2;
        }
    }
}

时间复杂度O(n) 空间复杂度O(1)

0 赞同 0 条回复

Yodl. 普通 2023年7月8日下午2:40

//法一：动态规划  时间复杂度O(n*n) 空间复杂度O(n)
class Solution {
public:
    int cuttingRope(int n) {
         /* 定义dp数组 */
        vector dp(n + 1);
        /* dp数组初始化 */
        dp[2] = 1;
        /* 从前向后遍历 */
        for (int i = 3; i <= n ; i++) {
            /* j遍历到小于i的值 */
            for (int j = 1; j < i - 1; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};


//法二：找规律 时间复杂度O(n) 空间复杂度O(1)
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;
        }
    }

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

0 赞同 0 条回复

yxy 普通 2023年7月8日下午2:25

时间复杂度O(n)

class Solution {
public:
    int cuttingRope(int n) {
        if(n==2) return 1;
        if(n==3) return 2;
        if(n==4) return 4;
        int res = 1;
        while(n>4)
        {
            n-=3;
            res*=3;
        }
        res*=n;
        return res;
    }
};

0 赞同 0 条回复

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

共以下 25 个回答

MY

# 回答此问题取消回复

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

共以下 25 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复