剪绳子，使得每段的长度乘积最大-Java基础

朱雀 2021-12-11 09:43 156阅读 0赞

**题目描述**

把一根绳子剪成多段，并且使得每段的长度乘积最大。

public class cutRope14 \{  
/\*\*  
 \* ycy  
 \* 题目描述:  
 \*   把一根绳子剪成多段，并且使得每段的长度乘积最大。  
 \* 解题思路：  
 \*   根据推理常理，要尽可能分解出多个长度为3的子绳子，并且最后不要出现1，只能出现2和3；  
 \*     
 \*/    
    public static int breakLength(int n)\{  //简单分解为多个3，2的  
        if(n<=3) return n;  
        int count1 = n/3;  
        if(n-count1\*3 == 1)\{  
            count1--;  
        \}  
        int count2 = (n-count1\*3)/2;  
        return (int) ((Math.pow(3, count1))\*(Math.pow(2, count2)));  
    \}  
    public static int DynamicbreakLength(int n)\{  //动态规划  
        int dbl\[\] = new int\[n+1\];  
        dbl\[1\] = 1;  
        for(int i=0;i<=n;i++)\{  
            for(int j=0;j<i;j++)//dbl\[i\]不分解，Math.max(j\*(i-j), dbl\[j\]\*(i-j))分解  
                dbl\[i\] = Math.max(dbl\[i\], Math.max(j\*(i-j), dbl\[j\]\*(i-j)) );  
        \}  
        return dbl\[n\];  
    \}  
    public static void main(String\[\] args) \{  
        int n = 19;          
        System.out.println("n result is "+breakLength(n));  
        System.out.println("n result is "+DynamicbreakLength(n));  
        int n1 = 3;          
        System.out.println("n1 result is "+breakLength(n1));  
    \}

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211211/78b6b1acc6c54853afce6b9ec3d88e85.png