算法学习之发现重叠子问题

题目要求：

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-break

解题代码：

class Solution {
private:
    vector<int> memo;

    int max3(int a, int b, int c) {
        return max(a, max(b, c));
    }

    // 将n进行分隔(至少分隔两部分)，可以获得的最大乘积
    int breakInteger(int n) {
        if (n == 1)
            return 1;

        if (memo[n] != -1) {
            return memo[n];
        }

        int res = -1;
        for (int i = 1; i <= n - 1; ++i) {
            // i + (n - i)
            res = max3(res, i * (n - i), i * breakInteger(n - i));
        }
        memo[n] = res;
        return res;
    }

public:
    int integerBreak(int n) {
        assert(n >= 2);
        memo = vector<int>(n + 1, -1);
        return breakInteger(n);
    }
};

动态规划解题代码：

class Solution {
private:
    int max3(int a, int b, int c) {
        return max(a, max(b, c));
    }

public:
    int integerBreak(int n) {
        assert(n >= 2);

        // memo[i]表示将数字i分割(至少分割成两部分)后得到的最大乘积
        vector<int> memo(n + 1, -1);
        
        memo[1] = 1;
        for (int i = 2; i <= n; ++i) {
            // 求解memo[i]
            for (int j = 1; j <= i - 1; ++j) {
                // j + (i - j)
                memo[i] = max3(memo[i], j * (i - j), j * memo[i - j]);
            }
        }
        return memo[n];
    }
};