【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();      }  };