整数拆分，减绳子（动态规划）

题目描述：

剑指Offer的减绳子和LeetCode的整数拆分都是这种类型的题，我感觉挺难的，看了好久题解，才迷迷糊糊懂点。唉，太菜了。

 public static int cutRope(int target){ //特殊的情况 if(target<=3) return target-1; int[] dp=new int[target+1]; dp[1]=1; dp[2]=2; dp[3]=3; //dp[i]中储存的元素不能小于i本身，一直往后赋值 for (int i = 4; i <target+1; i++) { //f(n) 等价于 max(1 * f(n - 1), 2 * f(n - 2), ..., (n - 1) * f(1))。 for (int j = 1; j <i ; j++) { dp[i]=Math.max(dp[i],dp[i-j]*j); } } return dp[target]; } 

本文地址：https://blog.csdn.net/qq_44900959/article/details/107621919