leetcode hot100 拆分整数

在本题目中，我们需要拆分一个整数n，让其拆分的整数积最大。因为每拆分一次都和之前上一次拆分有关系，比如拆分6可以拆成2x4，还可以拆成2x2x2，那么我们可以采用动态规划来做。

首先确定dp数组的含义，这里dp[i]表示将i拆分之后，所得的乘积为dp[i]。

然后确定递推公式，这里我们要思考，我们是要把i拆成若干个数，然后相乘，取最大值，也就是说，我们需要Math.max()。我们继续思考，如果拆成两个数，那就是把i拆成j和i-j，这两个数的乘积就是j*(i-j)。如果拆成三个或者四个或者更多，我们可以表示成jdp[i-j]。因为我们dp数组的定义就是把i-j拆成若干结果乘积最大。但我们还需要考虑，在我们拆之前，dp[i]这个数的大小，因为当我们开始遍历的时候，i是一个数字，那么我们就要考虑这个dp[i]。比如，我们要拆dp[10]，加入在拆到dp[6]的时候获得了最大值，那么之后，我们直接把4（10-6）直接拆成4个1即可。所以我们也要加入dp[i]。同时我们只需要拆i就可以了，不需要拆j了，如果我拆j的效果，其实是和拆（i-j）一样的，比如把6拆成4x2或者2x4，二者结果是一致的。所以递推公式应该是Math.max(dp[i],Math.max(j(i-j),j*dp[i-j]))。

然后我们进行初始化，题中说明n是正整数，所以dp[0]没有意义。dp[1]无法拆成两个正整数的和，所以也没有意义，dp[2] = 1。

然后确定遍历顺序，这里，我们是要先遍历i，然后在i确定的基础上，再把i进行拆分，然后再遍历j即可。

打印数组

class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i-j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}

原文地址：https://blog.csdn.net/buptlzl/article/details/136136315

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