剪绳子 -- java

给你一根长度为 n 的绳子，请把绳子减成 m 段（m、n都是整数，n > 1 并且 m > 1, 每段绳子的长度记为k[0], k[1],…,k[m]。

请问k[0]*k[1]k[2]…*k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成的长度为2、3、3三段，此时得到的最大乘积是18。

• 考察应聘者的抽象建模能力。应聘者需要把一个具体的场景抽象成一个能够用动态规划或者贪婪算法解决的模型。
• 考察应聘者对动态规划和贪婪算法的理解。能够灵活运用动态规划解决问题的关键是具备从上到下分析问题、从下到上解决问题的能力，而灵活运用贪婪算法则需要扎实的数学基本功。

设 f(n) 代表长度为n的绳子剪成若干段的最大乘积，如果第一刀下去，第一段长度是 i ，那么剩下的长度就是 n-i ，那么f(n)=max{f(i)f(n-i)}。假设f(i) 确定，我们就要继续求f(n-i)的最优解，我们可以看出剪绳子是最优解问题，其次，大问题包含小问题，并且大问题的最优解包含着小问题的最优解，所以可以使用动态规划求解问题，并且从小到大求解，把小问题的最优解记录在数组中，求大问题最优解时就可以直接获取，避免重复计算。

尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现，如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。

证明：

当 n >= 5 时，所有f(n)都可以表示为3(n - 3)或者2(n - 2)，又因为3(n - 3) - 2(n - 2) = n - 5 >= 0。因此把长度大于 5 的绳子切成两段，令其中一段长度为 3 可以使得两段的乘积最大。

当 n = 4时，拆成 2 * 2 最大。

public class MaxProductAfterCutting {
    public static int maxProductAfterCutting_solution1(int length) {
        // 得到 绳子长度小于等于3的显然的最优解
        if (length < 2) {
            return 0;
        } else if (length == 2) {
            return 1;
        } else if (length == 3) {
            return 2;
        }

        //创建数组存储子问题最优解
        int[] products = new int[length+1];
        for (int i = 0; i <= 3; i++) {
            products[i] = i;
        }

        int max = 0;
        // 开始求解每一个绳子长度的最优解
        for (int i = 4; i <= length; i++) {
            max = 0;
            for (int j = 1; j <= i/2; j++) {
                int product = products[j] * products[i-j];
                if (max < product) {
                    max = product;
                }
            }
            products[i] = max;
        }

        return products[length];
    }

    // 测试
    public static void main(String[] args) {
        System.out.println(maxProductAfterCutting_solution1(8));
    }
}

public class MaxProductAfterCutting {
    public static int maxProductAfterCutting_solution2(int length) {
        // 得到 绳子长度小于等于3的显然的最优解
        if (length < 2) {
            return 0;
        } else if (length == 2) {
            return 1;
        } else if (length == 3) {
            return 2;
        }

        // 尽可能多地剪去长度为3的绳子段
        int timesOf3 = length / 3;
        // 当绳子最后剩下的长度为4的时候，不能再剪去长度为3的绳子段
        // 此时更好的方法是把绳子剪成长度为2的两段，因为 2x2 > 3x1
        if ((length - timesOf3 * 3) == 1) {
             timesOf3--;
        }
        int timesOf2 = (length - timesOf3*3) / 2;
        return (int)(Math.pow(3, timesOf3)) * (int)(Math.pow(2, timesOf2));
    }

    // 测试
    public static void main(String[] args) {
        System.out.println(maxProductAfterCutting_solution2(8));
    }
}

如果面试题是求一个问题的 最优解（通常是求最大值或者最小值）（特点一），而且该问题 能够分解成若干个子问题（特点二），并且 子问题之间还有重叠的更小的子问题（特点三），就可以考虑用 动态规划 来解决这个问题。从上往下分析问题，从下往上求解问题，这是动态规划求解的问题的第四个特点。

当我们应用贪婪算法解决问题的时候，都一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。为什么某种贪婪选择能够得到最优解？ 这是我们应用贪婪算法时都需要问的问题，需要用数学方式来证明贪婪选择是正确的。

来自：
《剑指Offer》
Coding-Interviews/剪绳子.md at master · todorex/Coding-Interviews