整数拆分

宇宙之一粟

修改于 2023-09-23 17:42:05

1.4K0

修改于 2023-09-23 17:42:05

文章被收录于专栏：宇宙之_一粟

343. 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。

分析

分割4获得最大乘积拆分为：

1 + ？分割3获得最大乘积 --》 1+？分割2 ；2+？分割1 -- 》分割1

2+？分割2获得最大乘积

3+？分割1获得最大乘积

最优子结构：通过求子问题的最优解，可以获得原问题的最优解

一、递归

// @lc code=start
class Solution {

private:

    int max3( int a, int b, int c ) {
        return( a, max(b, c) );
    }
    // 将n进行分割（至少分割两部分），可以获得的最大乘积
    int breakInteger(int n) {

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

public:
    int integerBreak(int n) {

        return breakInteger(n);
    }
};
// @lc code=end

二、记忆化搜索

// @lc code=start
class Solution {

private:
    vector<int> memo;

    int max3( int a, int b, int c ) {
        return( 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 >= 1);
        memo.clear();
        for (int i = 0; i < n + 1; i ++)
            memo.push_back(-1);
        return breakInteger(n);
    }
};
// @lc code=end

// @lc code=start
class Solution {
private:

    vector<int> memo;

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

    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 ++ )
            res = max3( res, i*(n-i), i * breakInteger(n - i) );
        
        memo[n] = res;
        return res;
    }

public:
    int integerBreak(int n) {
        assert( n >= 1) ;
        memo = vector<int>(n+1, -1);
        return breakInteger(n);
    }
};
// @lc code=end

自底向上

// @lc code=start
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];
    }
};
// @lc code=end