营销型网站建设定制,手机设计免费软件,佛山百度seo代理,安徽公共资源交易中心剪绳子详解1.问题描述2.解题思路3.具体实现1.问题描述 2.解题思路
首先想到的思路#xff1a;因为是求乘积的最大值#xff0c;所以如果截取剩下的是1#xff0c;那还是它本身就没有意义。从此出发#xff0c;考虑绳子长度是2、3、4、5…通过穷举法来找规律。 值–》拆分–…
剪绳子详解1.问题描述2.解题思路3.具体实现1.问题描述 2.解题思路
首先想到的思路因为是求乘积的最大值所以如果截取剩下的是1那还是它本身就没有意义。从此出发考虑绳子长度是2、3、4、5…通过穷举法来找规律。 值–》拆分–》最大乘积 2 --》02 11 --》2 3 --》03 12 --》3 4 --》13 22 --》4 5 --》14 23 --》6 6 --》15 24 33 --》9 7 --》16 25 34 --》12 8 --》17 26 35 44 --》18 发现2,、3、4最大值都是他们本身5的最大值是可能拆成的数AB的A的最大值与B的最大值的乘积由此或许会联想到动态规划。但是用动态规划比较复杂首先需要将其拆分成两项(一直拆到有值/2的数出现)接着需要还需要对每个拆分项进行拆分(出口就是2、3、4)。 2.于是我接着思考是否还有哪些规律可以利用。因此我从最大值之间的联系与绳子长度进行分析 发现最大值一般都是在 n/2 附近出现的再进一步发现都是通过拆成3来实现最大值一直拆到最后一个值大于1因为拆成1没有意义。通过这个规律会发现代码实现就很容易了 6 33 321–9 32 7 34 322–12 322 8 17 26 35 44–18 332 9 18 27 36 45–27 333 3.具体实现
package offer230304;
import java.util.*;
/*** 剪绳子* 长度是n 1* 剪成整数长的m段 1 n在这里插入代码片* 每段绳子的长度是 k[1]....k[m]* * 可以想为是一个* 1* 2 11 02 --》2* 3 12 --3* 4 22 13 --4* 5 23 14--6* 6 33 321--9 32* 7 34 322--12 322* 8 17 26 35 44--18 332* 9 18 27 36 45--27 333* 10 19 28 37 46 55--36 334* 11 38 47 56 --54 3332* 拆成3而且最后不能是1,因为拆成1没有意义* 1--1 2--2 3--3* 4--4 31(3后面剩下的不能是1最少是2)* 》3的值似乎都是和3有关* author wen yang* 230304*/
public class JZ14 {public static void main(String[] args) {// TODO Auto-generated method stub//被我找到规律的Scanner scannernew Scanner(System.in);int target scanner.nextInt();//将它以3进行拆分剩下的如果不大于1那就不拆了ArrayListInteger partList new ArrayList();System.out.println(getMaxMul(target, partList));}public static int getMaxMul(int target,ArrayListInteger partList) {int maxMul1;int partTargettarget;//判断是否大于4,直接list的大小/*if(target4) {return maxMul*target;}*///进行拆分剩下的如果不大于1那就不拆了while(partTarget-31) {partList.add(3);partTarget-3;}//判断是否大于4,if(partList.size()0) {return maxMul*target;}//拆到最后的也加入集合中partList.add(partTarget);for(int i0;ipartList.size();i) {maxMul*partList.get(i);}return maxMul;}}
