【剑指Offer】T14 剪绳子(动态规划、贪婪算法)

长度为 n 的绳子,请把绳子剪成 m 段(m、n 都为整数,且都大于 1),每段绳子长度记为 k[0],k[1],...,k[m]。请问 k[0]x...xk[n] 最大乘积是多少?例如,长度为 8 时,剪为长度为 2、3、3 三段,最大乘积为 18。

思路:f(2)f(3)可以先求得,最优为 1、1 和 1、2。再把递归问题化为剩下的迭代

int maxProductAfterCutting_solution(int length){
    if(length < 2)
        return 0;
    if(length == 2)
        return 1;
    if(length == 3)
        return 2;
    
    int *products = new int[length+1]; // 每个长度下对应最大值(最优长度)
    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;
    
    int max = 0;
    
    for(int i = 4; i <= length; i++){ // 从长度4开始进行讨论,记录最大值
        max = 0;
        
        for(int j = 0; j <= i/2; j++){ // 对当前长度迭代所有情况,记录
            int product = products[j] * products[i-j]; // 裁剪长度乘以剩下长度
            if(max < product){
                max = product;
            }
        }
        products[i] = max;
    }
    max = products[length];
    delete[]products;
    return max;
}

贪婪算法的思路:

  • 长度大于 5 时,尽可能多剪长度为 3 的绳子
  • 剩下长度为 4 时,绳子剪为两个长度为 2 的绳子
int maxProductAfterCutting_solution(int length){
    if(length < 2)
        return 0;
    if(length == 2)
        return 1;
    if(length == 3)
        return 2;

    int timesOf3 = length / 3;
    if(length - timesOf3*3 == 1){
        timesOf3-=1;
    }
    
    int timesOf2 = (length - timesOf3*3)/2;
    
    return (int)(pow(3, timesOf3) * (int)(pow(2, timesOf2)));
}

1566223041921.png

本文链接:https://ariser.cn/index.php/archives/154/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!