《剑指offer》--014--剪绳子

刺骨的言语ヽ痛彻心扉 2022-06-01 10:16 195阅读 0赞

[《剑指offer》–目录索引][offer]

**题目：**

> 给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1）。每段的绳子的长度记为k\[0\]、k\[1\]、……、k\[m\]。k\[0\] \* k\[1\]\*…\*k\[m\]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

**前提：**

> 该题有两种解法：①动态规划；②贪婪算法  
> 个人觉得，这两个解法的区别就是：动态规划算出的结果准确，但是效率不算很好；贪婪算法的效率很高，但是算出的结果是近似值，不能说完全准确；  
> **在开始看思路和代码之前，还是需要弄懂什么是动态规划和贪婪算法？**可参看以下链接：  
> [个人推荐：白话算法之【动态规划入门】][Link 1]  
> 贪婪算法：可自行网上搜索，我的总结是，贪婪算法是用最小的数求得最大的值

**思路：**

> 动态规划：  
> ①首先划分子问题：设长度为n (n>=1)，第一次剪绳子，为了使乘积最大，减长度为i，表达式为f(n)=f(n-i)\*f(i);类似这样进入递归；  
> ②其次确定最终子问题的”状态“：当长度为1，2，3，4的时候，最大乘积都只有一中选择，分别对应为0，1，2，3；  
> ③最后看状态转移表达式，if(max < f(n)) \{max=f(n);\}，这个max的判断需要用一个循环来比较，比如想知道长度为5的绳子剪成两段，求最大乘积，代码可如下：

int max=0;
    for(int i=1;i<5/2;i++)
    {
        int tmp=(5-i)*i;
        if(max < tmp)
        {
            max =tmp;
        }
    }

**代码如下：**

int maxProductAfterCutting_solution1(int length) 
    {
        if (length < 2)
            return 0;
        if (length == 2)
            return 1;
        if (length == 3)
            return 2;
    
        int* products = (int*)malloc((length + 1)*sizeof(int));
        assert(products != NULL);
        memset(products, 0, (length + 1)*sizeof(int));
    
        /****长度为1、2、3、4的绳子的最大积********/
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;
    
        int max = 0;
        int i = 0;
        int j = 0;
    
        for (i = 4; i <= length; i++)
        {
            max = 0;
            for (j = 1; j <= i / 2; j++)
            {
                int product = products[j] * products[i - j];
                if (max < product)
                    max = product;
    
                products[i] = max;
            }
        }
        max = products[length];
    
        free(products);
        products = NULL;
    
        return max;
    }

> 贪婪算法：  
> 用最小的数求得最大的值，在这个题中可以转换成：用最短的绳子长度，得到最大的乘积，剪绳子的问题中，数值最小价值最大，就是指 2和3以及对应的2\*2=4 3\*3=9，因为2和3不能再拆分了，虽然不可拆分的数据有0 1 2 3，但是2 3的乘积相对来说最大，所以从2 3 两个角度出发 用贪婪算法得到近似最优解

**代码如下：**

int maxProductAfterCutting_solution2(int length) 
    {
        if (length < 2)
            return 0;
        if (length == 2)
            return 1;
        if (length == 3)
            return 2;
    
        int timesOf3 = length / 3;
    
        /* 当最后绳子长度为 4 时，这时候分割成 2，2 而不是 3，1 因为2*2=4 > 3=3*1 */
        if (length - timesOf3 * 3 == 1)
            timesOf3--;
    
        int timesOf2 = (length - timesOf3 * 3) / 2;
    
        return (int)(pow(3, timesOf3))*(int)(pow(2, timesOf2));
    }

[offer]: http://blog.csdn.net/w_y_x_y/article/details/79209805
[Link 1]: http://blog.csdn.net/u013445530/article/details/45645307