剪绳子

ryluo 2020-06-24 10:23:39

给你一根长度为 n绳子,请把绳子剪成 m 段(m、n 都是整数,2≤n≤58 并且 m≥2)。

每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少?

例如当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到最大的乘积18。

样例

输入:8

输出:18

分析:

将一个数分解成多个数的和,使得这些数的乘积最大。

切分规则:

  1. 最优:3。把绳子尽可能切为多个长度为3的片段,留下的最后一段绳子的长度可能为0,1,2三种情况
  2. 次优:2。若最后一段绳子为2,则保留,不在拆分为1+1
  3. 最差:1。若最后一段绳子为1,应该把一份3+1替换为2+2,因为2x2>3x1

证明链接:

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/

class Solution {
public:
    int maxProductAfterCutting(int n) {
        if (n <= 3) return n - 1;
        int res = 1;

        int a = n / 3, b = n % 3;

        if (b == 0) b = 1;
        else if (b == 1) a--, b = 4;

        while(a--) res *= 3;

        return res * b;
    }
};