《剑指offer》14题剪绳子

Java

题目描述

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

解题思路

思路一：贪心

假设k[0]-k[m]中有x个2，y个3，则有：
2x+3y=k
其乘积为：
$图片说明$
这是一个随y递增的函数，因此要保证最后的乘积最大，则y需要尽可能大，既3的个数要尽可能多
证毕，附代码如下：

public class Solution {
    public int cutRope(int target) {
        int sum = 1;
        if(target < 4){
            return target - 1;
        }
        while(target > 4){
            sum *= 3;
            target -= 3;
        }
        sum *= target;
        return sum;


    }
}

思路二：动态规划

动态规划求解问题的四个特征：
①求一个问题的最优解；
②整体的问题的最优解是依赖于各个子问题的最优解；
③小问题之间还有相互重叠的更小的子问题；
④从上往下分析问题，从下往上求解问题
因此可以从小的绳子的最值开始进行推演。
规律:

2和3不用拆
target的拆分结果中[任意几段]一定是[这几段对应的和长度]的最优解

任意一段长度大于3的绳子切割后一定可以得到比原来更优或者至少一样好的解
代码如下：

public class Solution {
public int cutRope(int target) {
 //特殊情况
 if (target<=3) return target-1;
 int[] ret = new int[target+1];
 ret[2] = 2;
 ret[3] = 3;
 for (int i=4; i<=target; i++){
     ret[i] = Math.max(ret[i-2]*2, ret[i-3]*3);
 }
 return ret[target];
}
}

另一种代码形式如下：

public class Solution {
 public int cutRope(int n) {
    // n<=3的情况，m>1必须要分段，例如：3必须分成1、2；1、1、1 ，n=3最大分段乘积是2,
     if(n==2)
         return 1;
     if(n==3)
         return 2;
     int[] dp = new int[n+1];
     /*
     下面3行是n>=4的情况，跟n<=3不同，4可以分很多段，比如分成1、3，
     这里的3可以不需要再分了，因为3分段最大才2，不分就是3。记录最大的。
      */
     dp[1]=1;
     dp[2]=2;
     dp[3]=3;

     for (int i = 4; i <= n; i++) {
         int res=0;//记录最大的
         for (int j = 1; j <=i/2 ; j++) {
             res=Math.max(res,dp[j]*dp[i-j]);//这里需要是两个dp值的乘积，而不是我之前想的j*dp[i-j]
         }
         dp[i]=res;
     }
     return dp[n];
 }
}
//这个多了循环

参考博客