343.整数拆分

本文主要是介绍343.整数拆分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

：数学推导，将n分为3a+b，乘积最大

复杂度 1 1

public int integerBreak(int n){if(n <= 3) return n - 1;int a = n / 3, b = n % 3;if(b == 0) return (int)Math.pow(3, a);if(b == 1) return (int)Math.pow(3, a - 1) * 4;return (int)Math.pow(3, a) * 2;
}

：dp算法，取dp[i] = j * Math.max(i - j, dp[i - j]);

复杂度 n*n n

public int integerBreak(int n){if(n <= 3) return n - 1;int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 1;dp[3] = 2;// dp[i] = j * Math.max(i - j, dp[i - j]);for(int i = 4; i <= n; i++){for(int j = 1; j <= 3; j++){dp[i] = Math.max(dp[i], j * Math.max(i - j, dp[i - j]));}}return dp[n];
}

这篇关于343.整数拆分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---