JZ67:剪绳子

剪绳子

http://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8

解法1:动态规划

  • 当n=1时,最大乘积只能为0;
  • 当n=2时,最大乘积只能为1;
  • 当n=3时,最大乘积只能为2;
  • 当n=4时,可以分为如下几种情况:1111,121,13,2*2,最大乘积为4;
  • 往下推时,发现n≥4时,可以把问题变成几个小问题,即:如果把长度n绳子的最大乘积记为f(n),则有:f(n)=max(f(i)*f(n-1)),0<i<n。所以思路就很容易出来了:从下往上推,先算小的问题,再算大的问题,大的问题通过寻找小问题的最优组合得到。

其实这就是动态规划法,以下是动态规划法的几个特点:

  1. 求一个问题的最优解
  2. 整体问题的最优解依赖各子问题的最优解
  3. 小问题之间还有相互重叠的更小的子问题
  4. 为了避免小问题的重复求解,采用从上往下分析和从下往上求解的方法求解问题
public int cutRope(int target){
        if(target==1){
            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;
        for(int i=4;i<=target;i++){
            int max=0;
            // 算不同子长度的乘积,找出最大的乘积
            for(int j=1;j<=i/2;j++){
                if(max<product[j]*product[i-j]){
                    max=product[j]*product[i-j];
                }
            }
            product[i]=max;
        }
        return product[target];
    }

解法2:贪心

贪婪算法依赖于数学证明,当绳子大于5时,尽量多地剪出长度为3的绳子是最优解。

public class Solution {
    public int cutRope(int target) {
        if(target<1){
            return 0;
        }
        if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        int count3=target/3;
        int count2=0;
        if(target%3==1){
            count3--;
        }
        count2=(target-count3*3)/2;
        return (int)(Math.pow(3,count3)*Math.pow(2,count2));
    }
}

解法3:暴力递归(超时)

public class Solution {
    public int cutRope(int target) {
        if(target<1){
            return 0;
        }
        if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        return getResult(target);
    }

    public int getResult(int target){
        if(target<4){
            return target;
        }
        int max=Integer.MIN_VALUE;
        for(int i=1;i<=target/2;i++){
            max=Math.max(max,i*getResult(target-i));
        }
        return max;
    }
}
剑指Offer题解 文章被收录于专栏

剑指Offer-Java版本题解

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议