DFS暴力搜索(超简单):
class Solution { public: int maxx; void dfs(int n,int mul){//n为目前还差的数量,mul是已经凑成的乘积 if(n==0||n==1){ //如果n还剩0或者1,那么说明已经凑够了n if(mul>maxx)maxx=mul; return; } for(int i=2;i<=n;i++){//从2开始是因为分出1的话,肯定会变小,比如4分出1还剩3,1*3<4所以不分1 dfs(n-i,mul*i); //-i说明凑出了一个i,然后乘积*i; } } int cutRope(int number) { maxx=0; if(number<=3)return number-1;//如果number小于等于3必须要分出一个1 dfs(number,1); return maxx; } };