一:題目

二:上碼

class Solution { public:/**思路:1.分析題意:將一個數拆分為幾個數相加的和 然后求取這幾個數相乘的最大積,這個就很動態規劃也就是我們可以得到多種結果，要在多種結果中取最優2.動態規劃:1>:確定dp數組代表啥，以及下標的含義dp[i]代表的就是最大乘積數,i代表的就是n2>:確定dp數組的狀態遞推公式我們將i劃分為多個數的和那么此時可以分為兩種情況(兩個數 / 多個數)兩個數: 我們將i劃分為 j 和 i-j(這里特別聲明j就是我們劃分的數值) ==> i = j + (i-j);多個數: 那就將i劃分為 j 但將(i-j)進行繼續劃分 ==> i = j + dp[i-j];這里我們的j的取值范圍是[1,i-1];(因為j是劃分的數值,那你最少得取值為1吧,同時也不能取值為i吧)dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));//因為j的數值不同,那么dp[i]也不同所以也要求取其最值3>:確定dp數組的初始化i>=2的 那么dp[2] = 1;4>:確定dp數組的遍歷順序肯定從前向后遍歷 (比如10 還需要用到3的最大乘積呢);5>:舉例驗證*/int integerBreak(int n) {vector<int>dp(n+1);dp[2] = 1;for(int i = 3; i <= n; i++) {//我們求取一個數的劃分后的最大乘積,那么肯定需要用到前面的數的最大乘積for(int j = 1; j < i-1; j++) {dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));}}return dp[n];} };

從沒思路 到看題解看不懂 再到看了好多題解懂了 再到自己寫出來 見證了我的喜怒哀樂
安 各位！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的leetcode343. 整数拆分(思路+详解)的全部內容，希望文章能夠幫你解決所遇到的問題。

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