【leetcode刷題】T167-整數拆分

• 2019 年 10 月 6 日
• 筆記

木又連續日更第3天（3/100）

木又的第167篇leetcode解題報告

動態規劃類型第12篇解題報告

leetcode第343題：整數拆分

https://leetcode-cn.com/problems/integer-break/

【題目】

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

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

【思路】

對於所有的j<i，dp[i] = max(dp[i], dp[j] * dp[i-j])

【程式碼】

python版本

class Solution(object):      def integerBreak(self, n):          """          :type n: int          :rtype: int          """          if n < 4:              return n-1          dp = [i for i in range(n+1)]          for i in range(4, n+1):              for j in range(1, i//2 + 1):                  dp[i] = max(dp[i], dp[j] * dp[i-j])          return dp[-1]  

C++版本

class Solution {  public:      int integerBreak(int n) {          if(n < 4)              return n-1;          vector<int> dp(n+1, 0);          dp[1] = 1;          dp[2] = 2;          dp[3] = 3;          for(int i=4; i < n+1; i++){              for(int j=1; j <= i/2; j++){                  dp[i] = max(dp[i], dp[j] * dp[i-j]);              }          }          return dp.back();      }  };