题目描述

剪绳子

样例

输入：8

输出：18

边界特殊样例

长度为0,1,2,3,4;

算法1

(动态规划)

今天也是抄作业的一天
说一下动态规划的三个特点吧
1. 求一个问题的最优解
2. 问题可以分割为求子问题的最优解，且求得方法相同
3. 子问题之间有很多重复的
这个题就符合上述的情况，求分割后的乘积最大，用数学表达式就是
$f(n) = max(f(i)*f(n-i)), i \in [0,n-1]$
从公式中可以看出满足上述三个特点

这里dp数组dp[i]表示长度为i的绳子剪完之后的最大乘积，
动态规划递推公式是dp[i] = max(j(i-j),jdp[i-j];

复杂度

时间复杂度 $O(n^2)$
空间复杂度 $O(n)$

参考文献

剑指offer 力扣 整数拆分

C++ 代码

int maxProductAfterCutting(int length) {
    vector<int> dp(length+1,0);
    /*数字0、1拆分是没有意义的*/
    dp[2] = 1;
    for(int i = 3; i <= length; ++i)
    {
        for(int j = 1; j < i-1; ++j)
            /*这里用找最大值的时候，要把dp[i]加进去
            因为上述的for j循环dp[i]是不断更新为最大值
            的，不知道是否已经是最大值了，如果已经是
            最大值了，就不需要更新了，那么max的结果就是
            本身*/
            dp[i] = max({dp[i],j*(i-j),j*dp[i-j]});
    }
    return dp[length];
}

算法2

(贪心策略)

在绳子长度n > 4时，按照每个长度为3的长度分就能得到最大的乘积
正确性需要严格的数学证明。

时间复杂度

时间复杂度 $O(n)$
空间复杂度 $O(1)$

参考文献

剑指offer

C++ 代码

int maxProductAfterCutting1(int length) 
{
    if(length == 2)
        return 1;
    if(length == 3)
        return 2;
    if(length == 4)
        return 4;
    int result = 1;
    while(length >= 0)
    {
        result *= 3;
        length -= 3;
        if(length <= 4)
        {
            result *= length;
            return result;
        }
    }
    return result;
}