18：剪绳子

r囧r小猫 2023-02-25 12:22 1阅读 0赞

#### 剪绳子： ####

一根长度为n的绳子，把绳子剪成m段，n>m>1且n>1，每段绳子的长度即为k\[0\],k\[1\]…k\[m\]，求k\[0\]\*k\[1\]…\*k\[m\]的最大乘积.

n是一个给定的绳子长度，m为未知

**动态规划：**

public class Offer19 { 
    
       public static void main(String[] args) { 
           System.out.println(maxProduct(7));
       }
    
       /** * 设置f(n)为绳子长度为n时的最大乘积，我们不知道剪几刀会是该绳子的最大乘积 * 现假设我们在离绳头i远的位置剪一刀，分为绳子a和绳子b，a绳长度为i，b绳长度为n-i，那现在的乘积为i*n-i，但是我们不知道这是不是最大乘积。 * 所以可得f(n) = max(f(i)*f(n-i)) */
       public static int maxProduct(int length){ 
           if(length==1)return 0;
           if(length==2)return 1;
           if(length==3)return 2;
           //长度为length，index最大为length-1
           int[] temp = new int[length+1];
           
           //数组前前三位装的是绳子剪之后可能存在的绳子的长度
           temp[1]=1;
           temp[2]=2;
           temp[3]=3;  
    
           int max = 0;
           //我们从绳子长度为4开始计算
           for(int i=4;i<=length;i++){ 
               max=0;
               //i/2的目的在于减少后面的重复
               for(int j=1;j<=i/2;j++){ 
                   int product = temp[j]*temp[i-j];
                   if(max<product)max=product;
                   temp[i]=max;
               }
           }
    
           max = temp[length];
    
           return max;
       }
    }

**贪婪算法：**

public static int maxNumber(int length) { 
            if (length < 2) { 
                return 0;
            }
            if (length == 2) { 
                return 1;
            }
            if (length == 3) { 
                return 2;
            }
            // 尽可能多去剪长度为3的绳子
            //计算长度为3的绳子数量
            int timesOf3 = length / 3;
            // 当最后剩下长度为4 的时候，绳子长度为3的段数减一
            if(length - timesOf3*3 == 1){ 
                timesOf3 --;
            }
    
            int timesOf2 = (length - timesOf3 * 3) / 2;
    
            return (int)Math.pow(3, timesOf3) * (int ) Math.pow(2, timesOf2);
        }