Q14_剪绳子.java

package com.algorithm.demo.剑指Offer;

/**
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。
 * <p>
 * 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
 * <p>
 * 例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18。
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
 * <p>
 * 假设剪的绳子那段称为 第一段，剪剩下的那段绳子称为 第二段，那么第一段的范围为 [2,i)，第二段可以剪或者不剪，假设 dp[i] 表示长度为 i 的绳子剪成 m 段后的最大乘积，那么，不剪总长度乘积为 j * （ i - j），剪的话长度乘积为 j * dp[ i - j ]，取两者的最大值，即 Max ( j * ( i - j) , j * dp[ i - j] )。
 * <p>
 * 2、规律
 * 长度为 n 的绳子剪掉后的最大乘积与求绳子长度为 n - 1 、 n - 2 、 n - 3 的最大乘积求法一样。
 * <p>
 * 不会剪长度为 1 的绳子下来。
 * 3、匹配
 * 通过规律可以发现，本题具备以下几个特征：
 * <p>
 * （1）是求最优解问题，如最大值，最小值；
 * （2）该问题能够分解成若干个子问题，并且子问题之间有重叠的更小子问题。
 * 动态规划！
 * <p>
 * 状态：dp[i]
 * <p>
 * 状态转移方程：dp[i] = Max(dp[i], Max(j * (i - j), j * dp[i - j]))
 * <p>
 * 4、边界
 * 长度为 1 的绳子
 * 长度为 2 的绳子
 */
public class Q14_剪绳子 {

    /**
     * 时间复杂度为 O(n2) 。
     * 空间复杂度为 O(n) 。
     *
     * @param n
     * @return
     */
    public int cuttingRope(int n) {
        //长度为 1 的绳子没法剪
        if (n <= 1) return 1;
        //用一个名为dp的数组来记录从 0 到 n 长度的绳子剪掉后的最大乘积
        //默认都是 0
        int[] dp = new int[n + 1];
        //由于绳子必须被剪，所以长度为 2 的绳子只有剪成 1 和 1 的两段，乘积结果为 1
        dp[2] = 1;
        //长度大于等于 3 的绳子才开始进入我们的讨论范围
        //从长度为 3 的绳子开始考虑，讨论它的最大乘积是多少，并不断的延伸绳子的长度
        for (int i = 3; i < n + 1; i++) {
            // 对于长度为 i 的绳子，它可以分为两个区间 j 和 i - j
            // j 的范围由 2 开始，因为剪长度为 1 的绳子无法扩大乘积的值
            // j 的范围可以延伸至 i - 1
            for (int j = 2; j < i; j++) {
                //不剪总长度乘积为 j * (i - j)
                //剪的话长度乘积为 j * dp[i - j]
                //取两者的最大值，即 Max(j * (i - j) , j * dp[i - j])
                //那么此时 dp[i] 的值取 i 不剪的值 (dp[i]) 和剪的值Max.max(j * (i - j)),
                //比如一开始 i = 3 , j = 2
                //dp[3] = Math.max(0 , Math.max(2 * 1, 2 * dp[1])
                //      = Math.max(0 , Math.max(2 , 2))
                //      = 2
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * (dp[i - j])));
            }
        }
        return dp[n];
    }

}