精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
最近各互联网大厂都已经开奖了，秋招基本告一段落，如果没收到offer的别急，还可以参加明年的春招。最近在上网的时候看到一个拼多多开奖的年包216万，吓我大跳，现在工资都这么高了吗？
我还特意查了一下，该岗位是大模型算法工程师，这个岗位工资本来就不低，和现在火热的AI有关，不过学历要求也比较高，大家争取都努努力，毕业之后也拿这个薪资。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第343题：整数拆分。
问题描述
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
输入: 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]));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];
}
public:
int integerBreak(int n) {
vector<int> 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];
}
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]
