343.整数拆分

刷题刷题找工作！

题目链接

DP入门之整数拆分！

题目：

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 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 - 1; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

为什么是两层for循环，因为每一个dp[i]都要慢慢拆成几个数，你可以理解一下，已经算到i了，所以后面的什么dp[j],dp[i-j]都已经获得了，就是在求最大值了，为什么会需要取dp[i]max一下，毕竟有的那么多的循环啊，要取一个和为最大的才能当作它的最终结果，好了理解了。

再问，为什么j<i-1,因为i-j的差距至少为2，dp[0]和dp[1]是无意义的。

再问，为什么拆分更好分成这两个？因为dp[i-j]的拆分数量是一定大于2个的，所以要把只拆分一个，即不拆分的单独提出来（之前写得，现在看不懂这句话了）

注意，max只有两个参数，写成这样三个会报错？是的，所以它是写成两个max来找最大

原文地址：https://blog.csdn.net/the_singular/article/details/125585698

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！