剪绳子

这道题的动态规划算法，真的是看《剑指Offer》这本书给弄晕了，剑指书上的解析是有问题的，后来看了牛客的题解和评论才分析明白。

public class Solution {
    public int cutRope(int n) {
        if (n == 2)
            return 1;
        if (n == 3)
            return 2;

        int[] p = new int[n+1];
        p[1] = 1;
        p[2] = 2;
        p[3] = 3;
        int max;
        for (int i = 4; i <= n; ++i) {
            max = 0;
            for (int j = 1; j <= i / 2; ++j) {
                int pro = p[j] * p[i - j];
                if (pro > max) {
                    max = pro;
                }
            }
            p[i] = max;
        }

       return p[n];
    }
}

注意，剑指书上说的p[i]存储的是f(i)即长度为i的绳子剪成若干段之后各段长度乘积的最大值，这个对于n >= 3而言是正确的，但是f(2) = 1, f(3) = 2，这个很显然和p数组中对应下标的值不同。

这是因为当我们基于p(n) = max(p(i) * p(n - i))求解乘积时，我们就要对p(2), p(3)独立看待，如果绳子的整长度是2或3，那么毫无疑问f(2) = 1, f(3) = 2，但是当绳子长度超过3时，我们将绳子分解为p(3)和p(n-3)时，p(3)用于乘法的值就是3而不是f(3)。理解了这个点，这个题目的动态规划版本也就不难理解了。