剑指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)，如果我们切一刀,变为n-i和i两段，
那么f(n)应该等于f(n-i)*f(i),所以在计算后面的f值的时候，会用到前面的f值，
所以对前面的结果进行保存。自底向上的得到我们最后的解。
然后考虑到类似于2,3,4这种其实不切一刀要比切一刀的结果更大，所以在计算f(n)的时候要将i*(n-i)考虑在内，意味着说这段如果只切一刀（切完的两端不再进行进一步的切割，比如4就切成2和2，而不是f(2)*f(2)）会得到一个什么样的结果。
所以综合以上考虑,对于长为n的绳子，f(n) = max(f(n-i)*f(i),(n-i)*i), i的取值从1到n-1;

解题代码

思路1代码

class Solution {
public:
    int cutRope(int number) {
        if(number == 2) return 1;
        if(number == 3) return 2;
        if(number == 4) return 4;
        if(number == 5) return 6;
        return 3*cutRope(number-3);
    }
};

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

思路2代码

class Solution {
public:
    int cutRope(int number) {
        // 方法2 ：dp
        vector<int> 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,(i-j)*j));
            }
        }
        return dp[number];
    }
};

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