02-26 12:39 南昌航空大学 Java 发布于江西
关注
动态规划：整数拆分
class Solution {
public int integerBreak(int n) {
int []dp=new int[n+1];
dp[2]=1; //dp[0]和dp[1]无意义，初始化dp2为1，因为递推公式与前面的有关，所以从前往后遍历
for (int i = 3; i <=n; i++) {
for (int j = 1; j <=i/2 ; j++) {
dp[i]=Math.max(dp[i],Math.max(dp[i-j]*j,j*(i-j))); //dp[i]表示从i为3开始到最后查找的最大，第三项表示只拆分一次，第二项表示可以拆分多次
}
}
return dp[n];
}
}
public int integerBreak(int n) {
int []dp=new int[n+1];
dp[2]=1; //dp[0]和dp[1]无意义，初始化dp2为1，因为递推公式与前面的有关，所以从前往后遍历
for (int i = 3; i <=n; i++) {
for (int j = 1; j <=i/2 ; j++) {
dp[i]=Math.max(dp[i],Math.max(dp[i-j]*j,j*(i-j))); //dp[i]表示从i为3开始到最后查找的最大，第三项表示只拆分一次，第二项表示可以拆分多次
}
}
return dp[n];
}
}
全部评论
相关推荐
05-25 22:29
天津大学 全栈开发 点赞 评论 收藏
分享
05-18 14:16
成都理工大学 C++ 努力的小明a：项目看着很眼熟，施磊老师吧，我也学的这个😋我当时是把rpc框架做成了一个分布式网盘，这是一个项目，然后muduo库做成集群即时通讯，又用QT做了个交互的客户端，这样又一个项目，然后一个轻量redis，一个CAD，总共四个项目，投了三个月就今天2月份一个小厂Qt offer，然后后面想开了，Qt啥的都能干，这个月get了个北京大厂的offer，做java后端，人生就是这么魔幻，现在就在去北京入职的路上
点赞 评论 收藏
分享
查看6道真题和解析