复杂度o(n)动态规划

JZ67 剪绳子
规律:

1. 2和3不用拆

2. target的拆分结果中[任意几段]一定是[这几段对应的和长度]的最优解

3. 任意一段长度大于3的绳子切割后一定可以得到比原来更优或者至少一样好的解

   public class Solution {
   public int cutRope(int target) {
   
       //特殊情况
       if (target<=3) return target-1;
   
       //规律:
       // 1. 2和3不用拆
       // 2. target的拆分结果中[任意几段]一定是[这几段对应的和长度]的最优解
       // 3. 任意一段长度大于3的绳子切割后一定可以得到比原来更优或者至少一样好的解
       int[] ret = new int[target+1];
       ret[2] = 2;
       ret[3] = 3;
       for (int i=4;i<=target;i++){
           ret[i] = Math.max(ret[i-2]*2,ret[i-3]*3);
       }
       return ret[target];
   }
   }