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

桎梏普通 2023年9月18日上午9:49

lass Solution {
    public int cuttingRope(int n) {
        //动态规划 
        //将整数i拆分为 j 和 i-j
        //dp[i] = max[ max(j*(i-j), j*dp[i-j]) ] 1<= j < i
        //dp[1] = 0
        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 条回复

June 普通 2023年9月7日下午9:33

class Solution {
    public int cuttingRope(int n) {
         if(n <= 1)
            return n;
        //dp[i] 表示将i拆分成至少两个正整数的和之后，这些正整数的最大乘积
        int[] dp = new int[n+1];
        dp[0] = 0; dp[1] = 0;
        for (int i=2 ; i <= n ; i++) 
        {
            int maxn = 0;
            for(int j = 0;j < i; j++)
            {
                maxn = Math.max(maxn, Math.max(j*(i-j) , j*dp[i-j]));
            }
            dp[i] = maxn;
        }
        return dp[n];
    }
}

0 赞同 0 条回复

hi 普通 2023年8月18日下午10:44

数学结论，分为2或3
在n%3为1时，再拿个3组成4

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

0 赞同 0 条回复

艺普通 2023年8月4日下午4:09

“`c++
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
int cuttingRope(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
if (n == 4) return 4;
int sum = 1;
while (n > 4) {
sum *= 3;
n -= 3;
}
sum *= n;
return sum;
}
};

0 赞同 0 条回复

CaCO3 永久会员 2023年8月3日上午9:02

”’java
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];
}

}
”’
时间复杂度O(n^2)
空间复杂度O(n)

0 赞同 0 条回复

#00456B 普通 2023年8月2日下午10:11

找规律

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

0 赞同 0 条回复

北辰普通 2023年8月1日下午8:44

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

时间复杂度：O（n2）
空间复杂度：O（n）

0 赞同 0 条回复

Marshan 普通 2023年8月1日下午5:27

数学推导

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

0 赞同 0 条回复

NullPointerException 普通 2023年7月31日下午4:46

class Solution {
public int cuttingRope(int n) {
//可以当做动态
//可以选择[n-k] * ([k]/k) 找出【k】的最长
int dp[]=new int [n+1];
dp[0]=0;
dp[1]=1;
dp[2]=1;
for(int i=3;i<dp.length;i++)
{
for(int j=2;j<i;j++)
{
dp[i]=Math.max(dp[i],Math.max(dp[i-j],i-j)*Math.max(dp[j],j));
}
}
return dp[n];
}
}

0 赞同 0 条回复

Mby 普通 2023年7月30日下午10:25

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;
        }
    }
    //这里可以直接调用Math.pow
    int pow(int a, int n){
        int sum = 1;
        for(int i = 1; i <= n; i++){
            sum = sum * a;
        }
        return sum;
    }
}

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月30日下午9:13

class Solution {
    public int cuttingRope(int n) {
        // 可以使用动态规划
        // 也可以找规律
        // 假如将一段绳子切成两端，两端相等时，乘积最大（不等式决定）
        // 长度为1，2，3，4时都不必切，但是由于至少切成两段，所以还是得切
        // 当长度为5时，切成2*3
        // 当同时存在2，3，4时。把2，4变成3*3
        // 也就是说，要尽可能切成3
        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;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月27日下午9:21

7.26
Day18：下面是代码

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

mpweixin用户普通 2023年7月27日下午3:19

//当 i>=2  时，假设对正整数 i 拆分出的第一个正整数是 j（1leji  ），则有以下两种方案：
        //将 i 拆分成 j 和 i-j 的和，且 i-j 不再拆分成多个正整数，此时的乘积是 j*(i-j);
        //将 i 拆分成 j 和 i-j 的和，且 i-j 继续拆分成多个正整数，此时的乘积是 j*dp[i-j];
        public int cuttingRope(int n) {
            int[] dp = new int[n+1];
            dp[1] = 1;
            for (int i = 2; i < n + 1; i++) {
                int curMax = 0;
                for (int j = 1; j < i; j++) {
                    curMax = Math.max(curMax, Math.max(dp[i-j]*j, j*(i-j)));
                }
                dp[i] = curMax;
            }

            return dp[n];

        }

0 赞同 0 条回复

CKX 普通 2023年7月26日下午11:30

func cuttingRope(n int) int {
    //dp[i]：将i拆分正整数后的最大乘积
    dp := make([]int, n+1)

    //base case
    dp[2] = 1

    //状态转移方程
    for i := 3; i <= n; i++ {
        for j := 1; j <= i-j; j++ {
            dp[i] = max(dp[i], j*dp[i-j], j*(i-j))
        }
    }


    return dp[n]
}

func max2(a, b int) int {if a > b {return a}; return b}
func max(a, b, c int) int {return max2(a, max2(b, c))}

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月26日下午9:37

代码

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=0;i<n;i++){
            sum = sum*a;
        }
        return sum;
    }

}

0 赞同 0 条回复

阿尚普通 2023年7月26日下午4:40

方法一：动态规划
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(Math.max(dp[j]*(i - j), j * (i - j)), dp[i]);
            }
        }

        return dp[n];
    }
}
O(n^2)

方法二：贪心算法
class Solution {
    public int cuttingRope(int n) {
        if(n < 4){
            return n - 1;
        }
        int res = 1;
        while(n > 4){
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
}
O(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;
    }
}
O(1)

0 赞同 0 条回复

Luminous 普通 2023年7月26日下午4:06

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

以上是代码

0 赞同 0 条回复

AD钙奶普通 2023年7月26日下午3:08

硬找规律
我写的时候，直接把长度从2 到 10的答案全部手算了一遍，然后根据某种方式进行分类，例如下面这种按照余数分类。

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n % 3, b = n / 3;
        if(a == 0) {
            // 6 9
            // 9 27
            return (int)Math.pow(3,b);
        }
        if(a == 1) {
            // 4 4
            // 7 12
            // 10 36
            return (int)Math.pow(3, b - 1) * 4;
        }
        // 5 6
        // 8 18
        return (int)Math.pow(3, b) * 2;
    }
}

0 赞同 0 条回复

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

共以下 18 个回答

# 回答此问题取消回复

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

共以下 18 个回答

# 回答此问题 取消回复

# 回答此问题取消回复