天津做网站外包公司,威海自适应网站建设,深圳百度开户,怎样在手机上无货源开店题目
给定一个正整数 n #xff0c;将其拆分为 k 个 正整数 的和#xff08; k 2 #xff09;#xff0c;并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n 2 输出: 1 解释: 2 1 1, 1 1 1。 示例 2:
输入: n 10 输出: 36 解释: 1…题目
给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n 2 输出: 1 解释: 2 1 1, 1 × 1 1。 示例 2:
输入: n 10 输出: 36 解释: 10 3 3 4, 3 × 3 × 4 36。
提示:
2 n 58
解析
dp[i]的定义:分拆数字i可以得到的最大乘积为dp[i] dp[i]的最大乘积可以通过2种方式得到 第一种2个数相乘 从1开始遍历j j*(i-j)—会被多次调用 第二种(多个数相乘) j*dp[i-j]
dp[i-j]为重叠子问题会被多次调用比如
dp[5](dp[6-1],dp[7-2]...)dp[7]为dp[2]*dp[5]与dp[3]*dp[4]等的最大值代码
import java.util.Scanner;public class IntegerSplit {public static int integerBreak(int n) {int[] dp new int[n1];dp[2] 1;for(int i 3; i n; i){for(int j 1; j i; j){dp[i] Math.max(Math.max(j*(i-j), j*dp[i-j]),dp[i]);}}return dp[n];}public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();System.out.println(integerBreak(n));}
}dp数组中的每一个元素都是经过一个不断扩大的循环计算出来的。
