剪绳子

思路：
此题看到最大，首先想到动态规划。难点在于递推方程。
我们假设n长度绳子的最大乘积为f（n），对于第一刀，我们有n-1种可能的选择，可推导出f(n)=max{f(i)*f(n-i)};

 //动态规划
    public int cutRope(int target){
        //当长度大于3 f[n]才能得到绳子的最大乘积因为target>1,m>1
        if(target==2){
            return 1;
        }
        if(target==3)return 2;
        int [] f = new int[target+1];
        f[0] = 0;
        f[1] = 1;
        f[2] = 2;
        f[3] = 3;
        for (int i = 4; i <f.length ; i++) {
            int max = 0;
            //计算f(n)*f(n-i)
            for (int j = 1; j <=i/2 ; j++) {
                int temp = f[j]*f[i-j];
                max = Math.max(temp,max);
            }
            f[i] = max;

        }

        return f[target];


    }