剑指Offer——剪绳子

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入描述:
输入一个数n，意义见题面。（2 <= n <= 60）
返回值描述:
输出答案。
示例

输入
8
返回值
18

题解

动态规划。用f(n)表示长度为n的绳子，最终的最大乘积。则
f(n)=max{1xf(n-1),2xf(n-2),...},f(n-1)=max{1xf(n-2),2xf(n-3),...}...，可以看出有重复的数据。因此可以采用记忆型动态规划。

public class Solution {
    public int cutRope(int target) {
        int[]res=new int[target+1];

        res[2]=1;// 长度为2的绳子必须割为1、1.

        for(int len=3;len<=target;++len){
            int max=0;
            for(int cut=1;cut<=len/2;++cut){
        // 当前绳子已经被割过了，即满足m>1。因此剩下的绳子可以选择割或者不割。
                int temp_1=res[cut]>cut?res[cut]:cut;
                int temp_2=res[len-cut]>len-cut?res[len-cut]:len-cut;
                int temp_max=temp_1*temp_2;
                max=max>temp_max?max:temp_max;
            }
            res[len]=max;// 当前绳子割的情况下的最大值
        }
        return res[target];
    }
}