【剑指offer系列】-14剪绳子（关键字：贪心算法、数学推导）

本文主要是介绍【剑指offer系列】-14剪绳子（关键字：贪心算法、数学推导），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

给一根长度为n的绳子，请把绳子剪成m段(m,n都是整数且1)，每段绳子的长度相乘最大乘积是多少？如绳子长度为8，当分别为2，3，3时，此时最大乘积18

1.思路：贪婪算法，每一步都可以做出一个贪婪的选择，基于此选择，我们能得到最优解

2.贪婪选择：

• n%3=0

     12/3=4，则s=3^4=81
  

• n%3=1

   	13/3=4余1，此时拿出一段3和余下的1，组成4 s=3^(4-1)*(3+1)
  

• n%3=2

   	13/3=4余2s=3^4*2		
  

3.代码

 		12 =>  (3^4)*(2^0)13 =>  (3^3)*(2^2)  14 =>	(3^4)*(2^1)	

public class Main14 {public static void main(String[] args) {int len = new Scanner(System.in).nextInt();System.out.println(maxMultip(len));}private static int maxMultip(int len) {if (len < 2)return -1;if (len ==2)return 1;if (len == 3)return 2;int timoeOf3 = len / 3;if (len - 3* timoeOf3 == 1)timoeOf3 -= 1;int timeOf2 = (len - 3 * timoeOf3) / 2;return (int)Math.pow(3,timoeOf3)*(int)Math.pow(2,timeOf2);}
}

这篇关于【剑指offer系列】-14剪绳子（关键字：贪心算法、数学推导）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---