专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近各互联网大厂都已经开奖了，秋招基本告一段落，如果没收到offer的别急，还可以参加明年的春招。最近在上网的时候看到一个拼多多开奖的年包216万，吓我大跳，现在工资都这么高了吗？
我还特意查了一下，该岗位是大模型算法工程师，这个岗位工资本来就不低，和现在火热的AI有关，不过学历要求也比较高，大家争取都努努力，毕业之后也拿这个薪资。
数据来源：OfferShow
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第343题：整数拆分。
问题描述
来源：LeetCode第343题
难度：中等
给定一个 正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
动态规划解决
这题是让把一个整数拆成 k 个正整数的和，让这 k 个正整数的乘积最大。这题有两种解决方式，一种是使用动态规划一种是使用数学知识解决，我们先来看下动态规划怎么解决。
首先我们定义数组dp[i]表示正整数 i 拆分之后所能得到的最大乘积。因为拆分的数字都是相乘，所以他们相乘的最后一步肯定是两个数的乘积，这里假设把 i 拆成两份，一份是 j ，另一份就是 i-j 。
每一份都有拆和不拆两种选择，所以总共有四种选择，我们取这四种选择乘积的最大值即可。
1， j 和 i-j 都不能再拆了，dp[i]=j*(i-j);
2，j 能拆，i-j 不能拆，dp[i]=dp[j]*(i-j);
3，j 不能拆，i-j 能拆，dp[i]=j*dp[i-j];
4，j 和 i-j 都能拆，dp[i]=dp[j]*dp[i-j];
把上面整理一下可以得到递推公式如下：
dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));那么这两份怎么分呢，我们可以让 j 从 1 开始，比如我们计算数字 9 拆分所能获得的最大乘积，画个图来看下：
要想计算数字 9，我们必须要先计算数字 8。对于数字 9 我们可以先分为两份，每一份都取最大值，然后相乘。
JAVA：
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;// 正整数1没法拆，我们默认他的值是1。
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {// j从1开始拆分
// 这里是递推公式
dp[i] = Math.max(dp[i], (Math.max(j, dp[j])) * (Math.max(i - j, dp[i - j])));
}
}
return dp[n];
}
C++：
public:
int integerBreak(int n) {
vector dp(n + 1, 0);
dp[1] = 1;// 正整数1没法拆，我们默认他的值是1。
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {// j从1开始拆分
// 这里是递推公式
dp[i] = max(dp[i], (max(j, dp[j])) * (max(i - j, dp[i - j])));
}
}
return dp[n];
}
Python：
def integerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1 # 正整数1没法拆，我们默认他的值是1。
for i in range(2, n + 1):
for j in range(1, i):
# 这里是递推公式
dp[i] = max(dp[i], (max(j, dp[j])) * (max(i - j, dp[i - j])))
return dp[n]
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。