欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

整数拆分,减绳子(动态规划)

程序员文章站 2022-09-21 09:06:53
题目描述:剑指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;...

题目描述:

剑指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