LeetCode:343. Integer Break 拆分整数保持乘积最大 - 日理万妓 2021-06-24 16:10 298阅读 0赞 **试题:** Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. Example 1: Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1. Example 2: Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Note: You may assume that n is not less than 2 and not larger than 58. **代码:** 拆分计算,一般都要考虑动态规划。对于乘积最大,我们要想办法将其拆解成子问题。对于3 × 3 × 4我们可以看成3 × (3 × 4),要想乘积最大,那么必须保持(3 × 4)乘积最大,不然就有更大的乘积。那么我们就找到了子问题:找到7=3+4的最大乘积。对于第一个3,我们不需拆分,因为不管乘积何种组合,我们总可以将第一项视为不拆分项,而将剩下的当成可拆分项。 class Solution { public int integerBreak(int n) { int[] dp = new int[n+1]; dp[1] = 1; for(int i=2; i<=n; i++){ for(int j=1; j<i; j++){ dp[i] = Math.max(dp[i], Math.max(j*(i-j),j*dp[i-j]) ); } } return dp[n]; } }
还没有评论,来说两句吧...