剑指offer-剪绳子

本文为剑指 offer 系列第六十四篇。
主要知识点为整数拆分，可以用贪心算法或者动态规划来解决。

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入描述:
输入一个数n，意义见题面。（2 <= n <= 60）
输出描述:
输出答案。

解题思路

思路1贪心算法

设绳长为n，则有如下的结论

1. n = 2,剪成2段，1*1 = 1
2. n = 3,剪成2段，1*2 = 2
3. n = 4,剪成2段，2*2 = 4
4. n = 5,剪成2段, 2*3 = 6
5. n = 6,剪成2段，3*3 = 9

当n > 5的时候3*(n-3)> 2*(n-2)
所以答案就是尽可能的多剪长度为3的段,同时不要长度为1的段;如果有1，那就和3一起拼成一个4，切割成2和2。

思路2动态规划

假设长度为n的绳子的最大乘积为f(n)。先切成i和n-i两段，保留长度为i的一段，另一段可以继续切，得到i*f(n-i)；也可以不再切，得到i*(n-i)。
这里一定要考虑不再切的情况，比如长度为4时，切成2和2就已经最好了。
所以对i从1到n-1分别计算max(i*f(n-i),(n-i)*i)，再取其中的最大值作为f(n)。把前面的结果保存下来，就可以自底向上得到最后的解。

解题代码

题目中的n可以到60，最大乘积为3486784401，已经超过32位int的范围，所以这里用long long保存和返回结果。

思路1代码

class Solution {
public:
    long long cutRope(int number) {
        if(number == 2) return 1;
        if(number == 3) return 2;
        if(number == 4) return 4;
        if(number == 5) return 6;
        if(number == 6) return 9; // 剩下的两个3不用再切
        return 3*cutRope(number-3);
    }
};

时间复杂度为O(n),空间复杂度为O(n)

思路2代码

class Solution {
public:
    long long cutRope(int number) {
        // 方法2 ：dp
        vector<long long> dp(number+1,0);
        dp[1] = 1;
        for(int i = 2; i<=number; i++){
            for(int j = 1;j<i;j++){
                dp[i] = max(dp[i],max(dp[i-j]*j,1LL*(i-j)*j));
            }
        }
        return dp[number];
    }
};

时间复杂度为O(n^2),空间复杂度为O(n)
以上，本题结束！