题目

leetcode:343

代码与解析

文章参考如下两篇文章
感谢两位大佬的博文,虽然流程还是没有太懂
1. carl代码随想录
2. 潇晨博客


视频题解
动态五部曲
– 1.确定dp下标及其含义

dp[i]为正整数i拆分之后的最大乘积

  • 2.确定递推公式
dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))

  • 3.dp初始化

  • 4.确定遍历顺序


dp[i] 是依靠 dp[i – j]的状态,所以遍历i一定是从前向后遍历,先有dp[i – j]再有dp[i]。

for i:=3;i<n+1;i++{
    for j:=1;j<i-1;j++{
        // i可以差分为i-j和j。由于需要最大值,故需要通过j遍历所有存在的值,取其中最大的值作为当前i的最大值,在求最大值的时候,一个是j与i-j相乘,一个是j与dp[i-j].
        dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))
    }
}
  • 5.打印dp


下面代码里为什么要有两个max呢, 因为下面的max函数写的只能接受两个参数

func integerBreak(n int) int {
    dp:=make([]int,n+1)
    // dp[1]=1
    dp[2]=1
    // 为了能取到n
    for i:=3;i<n+1;i++{
        for j:=1;j<i-1;j++{
// i可以拆分为i-j和j。由于需要最大值,故需要通过j遍历所有存在的值,取其中最大的值作为当前i的最大值,在求最大值的时候,一个是j与i-j相乘,一个是j与dp[i-j].
            dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))
        }
    }
    return dp[n]
}
func max(a,b int) int{
    if a > b{
        return a
    }
    return b
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:459551 人次
ICP备案号: 辽ICP备20003309号