[每日一道小算法（十九）][贪婪算法][动态规划] 剪绳子问题（剑指offer）

待我称王封你为后i 2023-07-04 11:25 41阅读 0赞

前言：  
这道题采用了两种解法，为了学习，所以都在此做一下记录。

### 题目描述 ###

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

### 题目解析 ###

### 贪婪算法 ###

这一道题准备使用贪婪算法，先说一下怎么实现的，当绳子长度大于等于5的时候，我们尽可能多地剪长度为2的绳子。当剩下的长度为4时，把绳子剪成两段长度为2的绳子。  
验证：当n>=5的时候，我们可以证明2（n-2）>n并且3（n-3）>n。也就是说，当绳子剩下的长度大于或者等于5的时候，我们就可把他减成长度为3或者2的绳子段。另外当n>=5时，3（n-3）>= 2(n-2),因此我们应该尽可能地多剪长度为3的绳子段。

#### 动态规划 ####

首先我们定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有n-1种可能的选择，也就是剪出来的第一大段绳子的可能长度分别为1，2，…，n-1。因此f(x)=max(f(i)\*f(n-i))，其中0<i<n。  
这是一个从上至下的递归公式。由于递归会有很多重复的子问题，从而有大量不必要的重复计算。一个更好的办法是按照从下而上的顺序计算，也就是我们先得到f(2)、f(3)，在得到f(4)、f(5)，直到得到f(n)。

### 代码样例 ###

#### 贪婪算法 ####

package com.asong.leetcode.CutTheRope;
    
    /** * 剪绳子 以下使用贪婪算法实现 * 具体： 当n>=5时，尽可能快的剪长度为3的绳子，当长度剩余4米的使用，减成2*2. */
    public class Solution { 
        public int cutRope(int target) { 
            if(target == 0)
            { 
                return 0;
            }
            if(target == 1)
            { 
                return 1;
            }
            if(target == 2)
            { 
                return 2;
            }
            //计算最多减了多少个3米
            int cutNumber = target/3;
            //
            if(target-cutNumber*3 == 1)
            { 
                cutNumber=cutNumber-1;
            }
            int two = (target-cutNumber*3)/2;
            return (int)Math.pow(3.0,(int)cutNumber)*(int)Math.pow(2.0,(int)two);
        }
    }

#### 动态规划 ####

public class Solution { 
        public int cutRope(int target) { 
            if(target<2)
            { 
                return 0;
            }
            if(target == 2)
            { 
                return 1;
            }
            if(target == 3)
            { 
                return 2;
            }
            int[] product = new int[target+1];
            product[0] = 0;
            product[1] = 1;
            product[2] = 2;
            product[3] = 3;
            int max = 0;
            for (int i = 4; i <= target; ++i) { 
                max = 0;
                for (int j = 1; j <= i/2; ++j) { 
                    int pro = product[j] * product[i-j];
                    if(max < pro)
                    { 
                     max = pro;   
                    }
                    product[i] = max;
                }
            }
            max = product[target];
            return max;
        }
    }