剪绳子

使用动态规划，dp[i]表示长度为i的绳子的最大乘积

public class Solution {
    public int cutRope(int target) {
        /*创建数组并初始化*/
        int[] dp = new int[target+1];
        dp[0] = 1;
        dp[1] = 1;
        //从长度为2的绳子开始遍历起
        for(int i = 2; i <= target; i++){
            //当长度没到target时，也可以不剪，为什么呢？因为到target显示至少需要剪一次，因为段数要大于1
            if(i != target)
                dp[i] = i;

            for(int j = 1; j < i; j++){
                //(长度为j的绳子的最大乘积 和 长度为i-j的绳子的最大乘积)的乘积  跟 不剪作比较
                // 取大的那个 即为长度为i的绳子的最大乘积
                dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
            }
        }
        return dp[target];
    }
}