首页 > 其他分享 >(动态规划)剑指 Offer 14- II. 剪绳子 II

(动态规划)剑指 Offer 14- II. 剪绳子 II

时间:2023-04-14 15:44:30浏览次数:46  
标签:14 Offer int res 绳子 II 长度

题目描述:

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。

请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

 

 

 

提示:

  • 2 <= n <= 1000

 

 

 

 

 

 

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        long res=1L;
        int p=(int)1e9+7;
        //贪心算法,优先切三,其次切二
        while(n>4){
            res=res*3%p;
            n-=3;
        }
        //出来循环只有三种情况,分别是n=2、3、4
        return (int)(res*n%p);
    }
}

 

标签:14,Offer,int,res,绳子,II,长度
From: https://www.cnblogs.com/zhz123567/p/17318508.html

相关文章

  • 2023-04-14 vue之组件全局注册
    新建一个vue文件,随便写点什么,然后在main.js中引入,如下:xxx.vue:<template><viewclass="container"><viewclass="content">登录窗口</view></view></template><script>exportde......
  • ABC214G/S2OJ1504
    ABC214G/S2OJ1504又是我不会的/hanx做了一天/ng直接做显然是不行的,所以考虑转化题意,对于\(\foralli\),连边\((A_i,B_i)\),现在题意就变成给边染色了,这样统计的就是不合法的,考虑容斥,一个很\(\text{naive}\)的容斥是总数-不合法,发现你根本做不了,所以很容易想到加强限制,让答......
  • 2023.4.14每日会议
    昨天做了什么:完成了对listview的item点击弹出详细信息,完成了图片识别微信支付截图录入遇到了那些问题:相机拍的照片太模糊,图片识别识别不出来今天打算做什么:根据用户消费比例给出消费建议,并且做总支付的图以及各项占比 ......
  • [LeetCode] 1440. Jump Game V 跳跃游戏之五
    Givenanarrayof integers arr andaninteger d.Inonestepyoucanjumpfromindex i toindex:i+x where: i+x<arr.length and 0< x<=d.i-x where: i-x>=0 and 0< x<=d.Inaddition,youcanonlyjumpfromindex i toi......
  • edu145-D
    题目链接:https://codeforces.com/problemset/problem/1809/D一个关键的地方没想到,没有想到枚举分界线。思路:最终改成的字符串的样子一定是这样的:以某个点为分界线,左边全是0,右边全是1。所以可以枚举分界线(分界线的值为1,左边去掉为1的,右边去掉为0的),当且仅当\(s_i=0,s_{i-1}=1\)交......
  • 动态规划:剑指 Offer 14- I. 剪绳子
    题目描述:给你一根长度为n的绳子,请把绳子剪成整数长度的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。  提......
  • 14面向对象
    面向对象面向对象编程介绍面向对象编程:ObjectOrientedProgramming,简称OOP,是一种程序设计思想。需要注意的是,与之对应的是面向过程编程思想。实际上,能够使用面向对象编程思想实现的程序,也都能通过面向过程完成。只是看哪种思想更适合当前开发需求。面向过程与面向对象区别面......
  • 40. 组合总和 II
    给定一个候选人编号的集合candidates和一个目标数target,找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。注意:解集不能包含重复的组合。classSolution{private:voidtraversal(vector<int>&candidates,......
  • winform-C#操作IIS_DirectoryEntry
    1、创建对象:DirectoryEntryrootfolder=newDirectoryEntry("IIS://localhost/W3SVC/1/ROOT"); //IIS://服务器的名字/要操作的Web服务器类型/站点/站点的虚拟目录 2、修改对象: 3、删除对象: 参考:   C#创建虚拟目录  C#使用DirectoryEntry操作IIS创建网站......
  • Linux中使用ntpdate同步失败报错:14 Apr 08:42:12 ntpdate[1255]: the NTP socket is i
    报错信息: 报错原因:1、可能是因为同步的域名信息没有解析到。2、可能是因为服务的问题导致没有同步成功。 解决方法:1、先关闭ntpd服务。[root@k8s-master01~]#servicentpdstopRedirectingto/bin/systemctlstopntpd.service 2、重新同步。[root@k8s-maste......