递归\动态规划

import java.util.ArrayList;
public class Solution {
    public int cutRope(int target) {
        if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        if(target==4){
            return 4;
        }

        //动态规划
        ArrayList<Integer> list = new ArrayList(){{
            add(0);
            add(1);
            add(2);
            add(3);
            add(4);
        }};

        for(int j=5; j<=target; j++){
            int max = 0;
            for(int i=2; i<=j/2; i++){
                if(list.get(i)*list.get(target-i)>max){
                    max = list.get(i)*list.get(target-i);
                }
            }
            list.add(max);
        }

        return list.get(target);


        /*
        //递归
        for(int i=2; i<=target/2; i++){
            int max1 = 0;
            int max2 = 0;
            if(i<=4){
                max1 = i;
            }else{
                max1 = cutRope(i);
            }

            if(target-i<=4){
                max2 = target-i;
            }else{
                max2 = cutRope(target-i);
            }            

            if(max1 * max2 > max ){
                max = max1 * max2;
            }
        }

        return max;
        */
    }
}