343. 整數拆分
力扣題目鏈接(opens new window)
給定一個正整數?n，將其拆分為至少兩個正整數的和，并使這些整數的乘積最大化。 返回你可以獲得的最大乘積。
示例 1:
- 輸入: 2
- 輸出: 1
- 解釋: 2 = 1 + 1, 1 × 1 = 1。
示例?2:
- 輸入: 10
- 輸出: 36
- 解釋: 10 = 3 + 3 + 4, 3 ×?3 ×?4 = 36。
- 說明: 你可以假設?n?不小于 2 且不大于 58。
思路：
從1到n遍歷， 拆分每一個數，拆分的過程可以使用動態規劃
動態規劃思路：
設dp[i] 是 i 拆分后的最大乘積，
dp[i]怎么得到？
其實可以從1遍歷j，然后有兩種渠道得到dp[i].
1、一個是j * (i - j) 直接相乘。 （拆成2個數）
2、一個是j * dp[i - j]，相當于是拆分(i - j)，（拆成大于2個數）
所以得到遞推公式：
dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j])注意： 初始化dp[2] = 1, 從i = 3開始遍歷
完整js代碼:
var integerBreak = function(n) {const dp = Array(n + 1).fill(0)dp[2] = 1// 遍歷從3到nfor(let i = 3; i <= n; i ++){// 遍歷從 1到i 來拆分ifor(let j = 1; j <= i; j ++){dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j])}}console.log(dp)return dp[n]
};
)
