leetcode343.整数拆分

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。

Solution

Step1.确定dp数组

dp[i]:拆分数字i，可以得到的最大乘积为dp[i]

Step2.确定递推公式

将j从1到i进行遍历

首先是dp[i]=j*(i-j)，这相当于拆成了两个数，一个是j，另一个是i-j

其次还可以是dp[i]=j*dp[i-j]，这相当于拆分了i-j

所以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

Step3.dp初始化

i取到的最小的有意义的值为2，dp[2] = 1；

Step4.确定遍历顺序

依旧是从小到大遍历

代码实现

class Solution {
public:
    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 / 2; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};