携程4月11日编程题 输出最大乘积 java

xiaoxiao2021-02-28  74

问题描述

有一个整数n,将n分解成若干个不同自然数之和,问如何分解能使这些数的乘积最大,输出这个乘积m

动态规划

根据题意,对于一个整数n,必然存在一个整数x,使得从n中分解出整数x可以使其最后获得最大乘积,这要求对n-x的分解也是最优解。我们用dp[i][j]表示从整数i分解出整数j的这种情况下,能达到的最大乘积。那么dp[i][j]可以递归的定义为

dp[i][j]={1max(dp[ij][k]j) i=0j<=i0<=k<j   构造一个二维数组dp,自底向上计算结果,最后通过查表得到最终结果。

对于给定的整数n,最后的最大乘积为

ans=maxdp[n][i]        0<=i<=n 

实现代码

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); //dp[i][j] 表示对i进行分解,从i中分解出整数j int[][] dp = new int[n+1][n+1]; for(int i = 0; i <= n; i++) dp[0][i] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ for(int k = 0 ; k < j; k++) dp[i][j] = Math.max(dp[i][j], dp[i - j][k] * j); } } //找到最大值 int ans = 0; for(int i = 0; i <= n; i++) ans = Math.max(ans, dp[n][i]); System.out.println(ans); //遍历输出整个二维数组 for(int[] d:dp){ System.out.println(Arrays.toString(d)); } } } }
转载请注明原文地址: https://www.6miu.com/read-56394.html

最新回复(0)