题目

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
}