【剑指Offer】JZ14--剪绳子

1.问题描述

2.解题思路

1. 首先想到的思路：因为是求乘积的最大值，所以如果截取剩下的是1，那还是它本身就没有意义。从此出发，考虑绳子长度是2、3、4、5…通过穷举法来找规律。

值–》拆分–》最大乘积
2 --》0+2 1+1 --》2
3 --》0+3 1+2 --》3
4 --》1+3 2+2 --》4
5 --》1+4 2+3 --》6
6 --》1+5 2+4 3+3 --》9
7 --》1+6 2+5 3+4 --》12
8 --》1+7 2+6 3+5 4+4 --》18

发现：2,、3、4最大值都是他们本身，5的最大值是可能拆成的数A+B的A的最大值与B的最大值的乘积，由此或许会联想到动态规划。但是用动态规划比较复杂，首先需要将其拆分成两项(一直拆到有值/2的数出现)，接着需要还需要对每个拆分项进行拆分(出口就是2、3、4)。

2.于是我接着思考，是否还有哪些规律可以利用。因此我从最大值之间的联系与绳子长度进行分析

发现：最大值一般都是在 n/2 附近出现的，再进一步发现都是通过拆成3来实现最大值，一直拆到最后一个值大于1，因为拆成1没有意义。通过这个规律会发现代码实现就很容易了
6 3+3 3+2+1–>9 3+2
7 3+4 3+2+2–>12 3+2+2
8 1+7 2+6 3+5 4+4–>18 3+3+2
9 1+8 2+7 3+6 4+5–>27 3+3+3

3.具体实现

package offer230304;
import java.util.*;
/*** 剪绳子* 长度是n >1* 剪成整数长的m段   >1 <=n`在这里插入代码片`* 每段绳子的长度是 k[1]....k[m]* * 可以想为是一个* 1* 2 1+1 0+2 --》2* 3 1+2 -->3* 4 2+2 1+3 -->4* 5 2+3 1+4-->6* 6 3+3 3+2+1-->9 3+2* 7 3+4 3+2+2-->12 3+2+2* 8 1+7 2+6 3+5 4+4-->18 3+3+2* 9 1+8 2+7 3+6 4+5-->27 3+3+3* 10 1+9 2+8 3+7 4+6 5+5-->36 3+3+4* 11 3+8 4+7 5+6 -->54  3+3+3+2* 	拆成3而且最后不能是1,因为拆成1没有意义* 1--1 2--2  3--3* 	4--4  3+1(3后面剩下的不能是1，最少是2)* 	》3的值似乎都是和3有关* @author wen yang* @230304*/
public class JZ14 {public static void main(String[] args) {// TODO Auto-generated method stub//被我找到规律的Scanner scanner=new Scanner(System.in);int target = scanner.nextInt();//将它以3进行拆分，剩下的如果不大于1，那就不拆了ArrayList<Integer> partList = new ArrayList<>();System.out.println(getMaxMul(target, partList));}public static int getMaxMul(int target,ArrayList<Integer> partList) {int maxMul=1;int partTarget=target;//判断是否大于4,直接list的大小/*if(target<=4) {return maxMul*target;}*///进行拆分剩下的如果不大于1，那就不拆了while(partTarget-3>1) {partList.add(3);partTarget-=3;}//判断是否大于4,if(partList.size()==0) {return maxMul*target;}//拆到最后的也加入集合中partList.add(partTarget);for(int i=0;i<partList.size();i++) {maxMul*=partList.get(i);}return maxMul;}}