分享
leetcode_343
淳属虚构 · · 962 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
Golang:
思路:这题以DP为思路,不算很难,以10为例子,我们知道结果是10=3+3+4这么拆分,如果我们假设res[i]表示i能拆分的正整数的最大乘积,那么如何计算res[10]呢?通过一个for循环,res[n]=res[i]*res[n-i],看看最大的res[n],即可。res[10]=res[3]*res[3]*res[4],实际上,也就是res[10]=res[3]*res[7]
代码如下:
func integerBreak(n int) int {
if n<=2 {
return 1
}
if n==3 {
return 3
}
arr:=make([]int,n+1)
//从5开始,所有的乘数i都可以被分解了
for i:=0;i<=4;i++{
arr[i]=i
}
for i:=5; i<=n; i++ {
temp:=i
for j:=2;j<=i/2;j++{
if arr[j]*arr[i-j]>temp {
temp=arr[j]*arr[i-j]
}
}
arr[i]=temp
}
return arr[n]
}
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信962 次点击
上一篇:leetcode_338
下一篇:leetcode_213
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
Golang:
思路:这题以DP为思路,不算很难,以10为例子,我们知道结果是10=3+3+4这么拆分,如果我们假设res[i]表示i能拆分的正整数的最大乘积,那么如何计算res[10]呢?通过一个for循环,res[n]=res[i]*res[n-i],看看最大的res[n],即可。res[10]=res[3]*res[3]*res[4],实际上,也就是res[10]=res[3]*res[7]
代码如下:
func integerBreak(n int) int {
if n<=2 {
return 1
}
if n==3 {
return 3
}
arr:=make([]int,n+1)
//从5开始,所有的乘数i都可以被分解了
for i:=0;i<=4;i++{
arr[i]=i
}
for i:=5; i<=n; i++ {
temp:=i
for j:=2;j<=i/2;j++{
if arr[j]*arr[i-j]>temp {
temp=arr[j]*arr[i-j]
}
}
arr[i]=temp
}
return arr[n]
}