应用动态规划求解问题的特点：
贪婪算法和动态规划不一样。应用贪婪算法解决问题时，每一步都可以做出一个贪婪的选择，基于这个选择，确定能够得到最优解。
思路1：动态规划。 （时间复杂度：O(n^2)， 空间复杂度：O(n)）
思路2：贪婪算法。 （时间复杂度：O(1)，空间复杂度：O(1)）
public class Solution { //动态转移的方程为：dp[n] = dp[n - i] * dp[i]，枚举i即可(1~n/2) public int cutRope(int target) { int[] dp = new int[target + 1]; // 0 ~ target if (target == 2) return 1; if (target == 3) return 2; dp[1] = 1; dp[2] = 2; dp[3] = 3; for (int i = 4; i <= target; i++) { for (int j = 1; j <= i / 2; j++) { dp[i] = Math.max(dp[i], dp[j]*dp[i-j]); } } return dp[target]; } }
Note： n<=3时，要分段。但是n>=4时，3就不要再分了，因为3分段要小于3，我们要记录最大的。
M
原文：https://www.cnblogs.com/HuangYJ/p/13673784.html