法1：动态规划

先贴个递归版本:

int cutRope(int n) {
    // write code here
    if(n <= 4) return n;
    int res = 0;
    for(int i = 1; i < n; i++){
        // 从i=1开始 表示第一刀剪下的长度
        res = max(res, max(cutRope(n-i)*i, i *(n-i)));
    }
    return res;
}

递归的化，用dp[i]表示长度为i的绳子可以被剪出来的最大乘积。 遍历维护从5到n的dp数组，用j来表示减下来的长度。

    int cutRope(int n) {
        // write code here
        if(n <= 4) return n;
        vector<int> dp(n+10);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        for(int i = 5; i<=n; i++){
            //i维护绳子长度
            for(int j = 1; j < i; j++){
                //j表示剪掉的长度
                dp[i] = max(dp[i], max(dp[i-j] * j, j *(i-j)));
            }
        }
        return dp[n];

    }

法2：数学结论
不断将绳子拆成每段长度为3，最后的结果就是最大的。

class Solution {
public:
    int cutRope(int number) {
        //不超过3直接计算
        if(number <= 3) 
            return number - 1;
        int res = 1;
        while(number > 4){
            //连续乘3
            res *= 3; 
            number -= 3; 
        }
        return res * number;
    }
};

2025年06月19日 14:50:53：完结