剑指offer014 剪绳子

Problem:

把一根绳子剪成多段，并且使得每段的长度乘积最大。

Intuition:

这一题比较容易，算是动态规划的开胃菜。首先我们聊一聊什么样的问题适合用动态规划。动态规划通常适合于要求我们求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个字问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决这个问题。下面的解法我们自己实现的方案既用了贪心算法的思想，也用了动态规划的思想。我们发现仅仅由dp[i-2],dp[i-3]就可以决定dp[i]里面的内容，原因是dp[i-p]（p>3）里面的内容一定是可以由dp[i-2]和dp[i-3]来表示的。举个简单的例子，如果最优解是要用到dp[i-4],那么接下里剩下的4肯定是切成22，那么这种情况就与dp[i-2]2的情况是完全一致的。如果是dp[i-5],那么剩下对于5的切法一定是23,这个和dp[i-2]3或者dp[i-3]*2就是一致的。依次类推，这时属于贪心算法的内容。接下来就用动态规划来存之前计算的结果就可以了。

Solution:

//dynamic programming+greedy algorithm
   public int cutRope(int length){
   	//dp[i]表示的就是长度为i的绳子对应的最大乘积，dp[0]没有意义
       int[] dp=new int[length+1];
       dp[0]=0;
       dp[1]=1;
       dp[2]=2;
       dp[3]=3;
       if (length <= 3) {
           return dp[length];
       }
       for(int i=4;i<=length;i++){
           //这里我们不用再写dp[i-4]*4的原因是dp[i-2]>=dp[i-4]*2,所以dp[i-4]的情况已经被包含在dp[i-2]的情况中了。
           dp[i]=Math.max(dp[i-2]*2,dp[i-3]*3);
       }
       return dp[length];
   }

   public int cutRope_D(int length) {

       if (length < 2) {
           return 0;
       }
       if (length == 2) {
           return 1;
       }
       if (length == 3) {
           return 2;
       }
       // 将最优解存储在数组中
       int[] products = new int[length + 1];
       // 数组中第i个元素表示把长度为i的绳子剪成若干段之后的乘积的最大值
       products[0] = 0;
       products[1] = 1;
       products[2] = 2;
       products[3] = 3;

       int max = 0;

       for (int i = 4; i <= length; i++) {
           max = 0;
           // 求出所有可能的f(j)*f(i-j)并比较出他们的最大值
           for (int j = 1; j <= i / 2; j++) {
               int product = products[j] * products[i - j];
               if (product > max) {
                   max = product;
               }
               products[i] = max;
           }
       }
       max = products[length];

       return max;
   }