[数据结构与算法]剑指Offer 14. 剪绳子

题目描述：
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问$k[1]\times ...\times k[m]$可能的最大乘积是多少？例如，当绳子的长度是8时，把它剪成长度分别为2、3、3的三段，得到的最大乘积是18。
示例1：

输入：8
返回值：18
输入描述：输入一个数n，意义见题面。（2 <= n <= 60）
返回值描述：输出答案。

方法一：动态规划
动态规划和递归类似，有如下特点：(1)一般用于求最优解(最大值、最小值)；(2)整体问题的最优解依赖于各个子问题的最优解，也就是大问题可以分解成各个子问题；(3)小问题之间还存在相互重叠的更小子问题，对于递归，则会存在重复计算，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。(4)从上往下分析问题，从下往上求解问题。

假设把长度为$n$的绳子剪成若干段，各段长度乘积的最大值为$f(n)$。第一次剪后，绳子变成两段，假设第一段长为 i，则第二段长为(n - i)，且$1<=i<=n?1$，对于长度为 i 和 (n - i) 的两段绳子可再继续剪下去，这是一个从上往下递归的过程，容易得到：
$f(n)=max(f(i)\times f(n?i))$。这可以通过递归来实现，但是会存在重复计算问题，例如$f(7)$分为$f(2)$和$f(5)$两个子问题，$f(5)$又能分为$f(2)$和$f(3)$两个子问题，这里$f(2)$就会重复计算。为了避免递归的重复计算问题，可以使用动态规划来解决，从下往上求解各个子问题，并把子问题的解缓存起来，通常是缓存在一维数组或二维数组中。

为了求解$f(i)$，需要求出所有可能的$f(j)\times f(i?j)$的值，并比较得出它们中的最大值，存放在dp数组对应位置。

public class Solution {
    public int cutRope(int target) {
        if (target == 1) return 0;
        if (target == 2) return 1;
        if (target == 3) return 2;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= target; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
        }
        return dp[target];
    }
}

时间复杂度：双层for循环，$O(n^2)$；空间复杂度：开辟了一个数组空间，用于缓存子问题结果，$O(n)$。

方法二：贪心算法

public class Solution {
    public int cutRope(int target) {
        if (target == 1) return 0;
        if (target == 2) return 1;
        if (target == 3) return 2;
        int a = target / 3;
        int b = target % 3;
        if (b == 0) return (int) Math.pow(3, a); //pow()方法返回的类型是double，需要强转成int
        if (b == 1) return (int) Math.pow(3, a - 1) * 4;
        return (int) Math.pow(3, a) * 2;
    }
}

时间复杂度：$O(1)$，空间复杂度：$O(1)$。

结束语：如果本篇博客对您有帮助，请点赞、收藏或关注，您的鼓励是博主进步的动力，感谢支持，共同进步。