【算法与数据结构】343、LeetCode整数拆分-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法与数据结构】343、LeetCode整数拆分。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

【算法与数据结构】343、LeetCode整数拆分,算法,算法

二、解法

思路分析：博主做这道题的时候一直在思考，如何找到 $k$ 个正整数， $k$ 究竟为多少合适。从数学的逻辑上来说，将 $n$ 均分为 $k$ 个数之后， $k$ 个数的乘积为最大（类似于相同周长下，正方形的面积大于长方形，严格的数学证明不深究了）。本题如果用动态规划的方式，令 $d p [i]$ 表示为最大的整数乘积，那么一定可以找到一个 $d p [i - j]$ ，使得 $d p [i - j] * j$ 最大，并赋值给 $d p [i]$ 。而 $d p [i - j]$ 又可以进行类似操作，那么可以一直追溯到 $d p [0], d p [1], d p [2]$ 。当然，本题当中 $d p [0], d p [1]$ 没有意义， $d p [2] = 1$ 。除了 $d p [i - j] * j$ 可以得到 $d p [i]$ 以外， $(i - j) * j$ 也可以得到 $d p [i]$ ，然后我们在每次递归的过程中比较上次的 $d p [i]$ 找到最大值。因此， $d p [i] = ma x (d p [i], ma x (d p [i - j] * j, (i - j) * j))$ 。同时，因为0和1没有意义， $i$ 从3开始循环，到 $n$ 。 $j$ 只要循环到 $i /2$ 即可。
程序如下：

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];
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ 。
空间复杂度： $O (n)$ 。

三、完整代码

# include <iostream>
# include <vector>
using namespace std;

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];
    }
};

int main() {
	Solution s1;
	int n = 10;
	int result = s1.integerBreak(n);
	cout << result << endl;
	system("pause");
	return 0;
}