前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【剑指Offer】14. 剪绳子

【剑指Offer】14. 剪绳子

作者头像
瑞新
发布2020-12-07 14:23:52
3070
发布2020-12-07 14:23:52
举报
文章被收录于专栏:用户3288143的专栏

题目描述

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

代码语言:javascript
复制
n = 2
return 1 (2 = 1 + 1)

n = 10
return 36 (10 = 3 + 3 + 4)

解题思路

贪心

尽可能多剪长度为 3 的绳子,并且不允许有长度为 1 的绳子出现。如果出现了,就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合,把它们切成两段长度为 2 的绳子。

证明:当 n >= 5 时,3(n - 3) - n = 2n - 9 > 0,且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情况下,将绳子剪成一段为 2 或者 3,得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) = n - 5 >= 0,所以剪成一段长度为 3 比长度为 2 得到的乘积更大。

代码语言:javascript
复制
public class Solution {
    /**
    * 解题思路,找出最优解的规律
    * 当target等于1,2,3的时候,结果是固定的
    * 当target大于3的时候,可以看以下数据
    * target=4, 最优解:2 2
    * target=5, 最优解:3 2
    * target=6, 最优解:3 3
    * target=7, 最优解:3 2 2
    * target=8, 最优解:3 3 2
    * target=9, 最优解:3 3 3
    * target=10,最优解:3 3 2 2
    * target=11,最优解:3 3 3 2
    * target=12,最优解:3 3 3 3
    * target=13,最优解:3 3 3 2 2
    * target=14,最优解:3 3 3 3 2
    * target=15,最优解:3 3 3 3 3
    *
    * 所以不难发现3和2的个数规律
    */
    public int cutRope(int target) {
        if(target < 2)
            return 0;
        if(target == 2)
            return 1;
        if(target == 3)
            return 2;
        
        int of3 = target / 3;
        if(target - of3 * 3 == 1)
            of3--;
        int of2 = (target - of3 * 3) / 2;
        
        return (int)(Math.pow(3, of3)) * (int)(Math.pow(2, of2));
    }
}

动态规划

代码语言:javascript
复制
public class Solution {
    public int cutRope(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
            for (int j = 1; j < i; j++)
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
        return dp[n];
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/08/08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 解题思路
    • 贪心
      • 动态规划
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档