剪绳子

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

解题思路

使用动态规划来解决这道题目。考虑一点：如果分段数为 target，那么必然有一个点，把 target 分成两段，两段分别构成最小子问题。而这两段的最大值的乘积，也就是 target 所求的最大值。

设划分点为 i，f[i] 表示长度为 i 的绳子的乘积最大值。可得转移方程：f[i] = MAX{f[j]*f[i-j]}，其中 0 < j < i

public class Solution {
    public int cutRope(int target) {
        int[] f = new int[target + 1];
        // 初始化
        f[0] = 0;
        f[1] = 1;
        for (int i = 1; i <= target; i++) {
            /**
             * 处理不分割的情况，假设有f[6]
             * 那么f[6]的最大乘积是3*3=9，那么f[3]就不能被分割了
             * 如果f[i] = i，证明最大就是它本身
             * 除非到了target，否则不能分割
             * 至于i==target将f[i]=1，是防止target本身就是最大
             */
			if(i==target) {
                f[i] = 1;
            }else {
                f[i] = i;
            }
            for (int j = 1; j < i; j++) {
                f[i] = Math.max(f[i],f[j]*f[i-j]);
            }
        }
        return f[target];
    }
}