剪绳子

题目：给你一根长度为 的绳子，请把绳子剪成 段( 都是整数，)，每段绳子的长度记为 。请问 可能的最大乘积是多少? 例如当绳子的长度是 时，我们把它剪成长度分别为 的三段，此时得到的最大乘积是 。

我们定义长度为 的绳子剪成若干段后，所能得到的最大长度为 。如果我们将绳子一段剪为长度为 和 ，那么这时长度为 能够被剪成的乘积是：长度为 能够剪成的乘积 × 长度为 能够剪成的乘积，因为 和 分别表示长度为 和 能够剪成的乘积最大值，所以这时长度为 能够被剪成的乘积的最大值是 ，所以 。所以我们只要遍历 ，找出所有 中的最大值，这个值便是 。

为了求出 ，我们还需要知道 这些初始值。当长度为 时，只能剪成两段都为 的两段，这时乘积的长度为 ；当长度为 时，可以被剪成 和 的两段或者三段为 的三段，因为 ，所以 。

代码如下：

public class Cut {
    public static int cut(int n) {
        if (n < 2) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }
        // 使用 results 数组保存 f(2) f(3) ... f(n)
        // results[n] = f(n)
        int[] results = new int[n + 1];
        results[0] = 0;
        // results[1] = 1 而不是 0 因为已经被切成两段，所以这里可以不继续切
        results[1] = 1;
        // results[2] = 2 而不是 1 也是同理
        results[2] = 2;
        // results[3] = 3 而不是 2 也是同理
        results[3] = 3;
        for (int i = 4; i <= n; i++) {
            int max = 0;
            // 遍历所有 j，
            for (int j = 1; j <= i / 2; j++) {
                int result = results[j] * results[i - j];
                if (max < result) {
                    max = result;
                }
            }
            results[i] = max;
        }
        return results[n];
    }
    public static void main(String[] args) {
        System.out.println(cut(8)); // 18
    }
}

总结： 我们将一个大问题切分为多个小问题，并且将小问题的解组合起来得到大问题的解，这样的解法我们称之为动态规划。如果题目是求一个问题的最优解(通常是最大值或最小值)，并且该问题可以被分为若干个子问题，子问题之间还有重叠的更小的问题，那么就考虑可以使用动态规划的解法。

在使用动态规划求解问题最优解时，为了防止多次重复计算子问题，我们一般会先将子问题的最优解存储下来，再根据此来计算问题的最优解。我们在之前的斐波那契数列的求解过程中，便是将原来的前两项值先保存下来，然后计算后一项的值；在上面的问题中，我们也是使用 results 数字将子问题的最优解保存下来，然后据此计算最优解。

所以在使用动态规划解决问题时，我们往往从上往下分析问题，找到问题最优解与子问题最优解之间的关系，然后从下往上求解问题，存储子问题的最优解，以防产生重复的计算。