題目描述
給你一根長度為n的繩子，請把繩子剪成整數長的m段（m、n都是整數，n>1并且m>1），每段繩子的長度記為k[0],k[1],...,k[m]，請問k[0]xk[1]x...xk[m]可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18，輸入描述:
輸入一個數n，意義見題面，（2 <= n <= 60）
輸出描述:
輸出答案，示例1
輸入
復制8
輸出
復制18
思路：可以知道2的話，此時應輸出1，3的話應輸出2，其他的值都能分解，比如8，可以分解為2+6和3+5，可以再分割如下：
2+6=2+2+4或2+3+3
2+2+4還可以分解為2+2+2+2.
3+5=3+2+3
可以看到，當分解到3和2時，就不需要再向下分解了，代碼如下：
class Solution {public: int cutRope(int number) { if(number<=2) return 1; if(number==3) return 2; int max=number; for(int i=0;i<=1;i++) { int temp=(i+2)*(number-i-2); if(temp>max) max=temp; if(max<(cutRope(i+2)*cutRope(number-i-2)) ) { max=cutRope(i+2)*cutRope(number-i-2); } } return max; }};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3835.html
標籤：其他
下一篇：滑動視窗的最大值