描述

343. 整數拆分
給定一個正整數 n，將其拆分為至少兩個正整數的和，并使這些整數的乘積最大化。 返回你可以獲得的最大乘積。

示例 1:

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
說明: 你可以假設 n 不小于 2 且不大于 58。

思路：動態規劃

class Solution { public:int integerBreak(int n) {//1.定義一個dp數組vector<int> dp(n+1); //其中i表示拆分i最大乘積dp[i]//2.初始化數組dp[2]=1;//3.進行遍歷for(int i=0;i<=n;i++){for(int j=1;j<i-1;j++){dp[i] = max(dp[i], max((i-j)*j,dp[i-j]*j));}}return dp[n];} };

總結

以上是生活随笔為你收集整理的LeetCode-动态规划基础题-343. 整数拆分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。