專欄：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算法文檔 。