LeetCode 343. 整数拆分
题目描述
思路分析
- 这个问题可以使用动态规划来解决。我们可以定义一个动态规划数组 dp，其中 dp[i] 表示正整数 i 拆分后的最大乘积。
- 我们从小到大遍历正整数 i，对于每个 i，我们需要找到它的最大拆分乘积 dp[i]。为了求解 dp[i]，我们可以遍历 j 从 1 到 i-1，将 i 拆分为两个正整数 j 和 i-j，然后找到 j 和 dp[i-j] 的乘积的最大值。因此，dp[i] 的状态转移方程为：dp[i] = max(dp[i], j * dp[i-j])
- 这里的 j * dp[i-j] 表示将 i 拆分为 j 和 i-j 两个正整数的乘积，然后取最大值。我们要遍历所有可能的 j，找到 dp[i] 的最大值。
- 最终，dp[n] 就是正整数 n 拆分后的最大乘积。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func integerBreak(n int) int {
dp := make([]int, n+1)
// dp[i] 表示正整数 i 拆分后的最大乘积
for i := 2; i <= n; i++ {
for j := 1; j < i; j++ {
// 将 i 拆分为 j 和 i-j，然后找到 j 和 dp[i-j] 的乘积的最大值
dp[i] = max(dp[i], j*max(i-j, dp[i-j]))
}
}
return dp[n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！