【剑指offer】面试题14 - 减绳子

深碍√TFBOYSˉ_ 2022-11-06 07:52 95阅读 0赞

### 文章目录 ###

*  面试题14：减绳子
 *   *  解法一：动态规划
     *  解法二：贪心算法

# 面试题14：减绳子 #

题目描述：

> 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k\[1\],…,k\[m\]。请问k\[1\]x…xk\[m\]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
> 
> 题目链接：[LeetCode][] [牛客网][Link 1]

## 解法一：动态规划 ##

> 公式：  
>  f ( n ) = m a x ( f ( i ) ∗ f ( n − i ) ) , 其 中 i ∈ \[ 1 , i / 2 \] , n > = 4 f(n) = max(f(i)\*f(n-i)) ,其中i∈\[1,i/2\],n>=4 f(n)=max(f(i)∗f(n−i)),其中i∈\[1,i/2\],n>=4  
> 当 n=1 时，没有意义的参数
> 
> 当 n=2 时，切成 1 \* 1
> 
> 当 n=3 时，切成 1 \* 2
> 
> 当 n=4 时，切成 1 和 3，或者，切成 2和 2，所以取其中最大的是 2 \* 2
> 
> 当 n=5 时，切成 1 和 4，或者，切成 2和 3，其中 4 可以被切成乘积最大的 4 ，取其中最大的是 2 \* 3
> 
> 当 n=6 时，切成 1 和 5，或者，切成 2 和 4，或者，切成 3 和 3，其中 4 可以被切成乘积最大的 2 \* 2，其中5可以被切成乘积最大的 2 \* 3，所以取其中最大的是切成 2 和 4 ，即 2 \* 2 \* 3

class Solution { 
    public:
        int cuttingRope(int n) { 
            // n<=3 时，需要特殊处理
            if(n < 2) return 0;
            if(n == 2) return 1;
            if(n == 3) return 2;
            //初始化用于存储中间值的数组 v
            vector<int> v;
            v.resize(n + 1);
            for(int i = 0; i <= 3; i++)
                v[i] = i;
            //当n=4时，数组中的值才是正确的
            for(int i = 4; i <= n; i++)
            { 
                int Max = 0;
                for(int j = 1; j <= i/2; j++)
                { 
                    Max = max(Max, v[j] * v[i - j]);
                    v[i] = Max;
                }
            }
            return v[n];
        }
    };

## 解法二：贪心算法 ##

> 思路：
> 
> 当 n >= 5 时，将绳子尽可能多的剪成长度为 3 的绳子
> 
> 当剩下的绳子长度为4时，把绳子剪成两段长为 2 的绳子

class Solution { 
    public:
        int cuttingRope(int n) { 
            if(n < 2)
                return 0;
            if(n == 2)
                return 1;
            if(n == 3)
                return 2;
            int timesOfThree = n / 3;
            if(n - timesOfThree * 3 == 1)    // 2*2 > 3*1
                timesOfThree -= 1;
            int timesOfTwo = (n - timesOfThree * 3) / 2;
            return pow(3, timesOfThree) * pow(2, timesOfTwo);
        }
    };

[LeetCode]: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/submissions/
[Link 1]: https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8?tpId=13&tqId=33257&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey