当前位置: 首页 > news >正文

嵩明网站建设深圳食品网站建设

嵩明网站建设,深圳食品网站建设,wordpress悬浮按钮,做网站 接活343. 整数拆分 给定一个正整数 n #xff0c;将其拆分为 k 个 正整数 的和#xff08; k 2 #xff09;#xff0c;并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n 2 输出: 1 解释: 2 1 1, 1 1 1。示例 2: 输入: n 10 输出: 36…343. 整数拆分 给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n 2 输出: 1 解释: 2 1 1, 1 × 1 1。示例 2: 输入: n 10 输出: 36 解释: 10 3 3 4, 3 × 3 × 4 36。提示: 2 n 58 思路(动态规划) 法一 对于正整数 n当 n ≥ 2 时可以拆分成至少两个正整数的和。令 x 是拆分出的第一个正整数则剩下的部分是 n − xn − x 可以不继续拆分或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积因此可以使用动态规划求解。 创建数组 dp其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后这些正整数的最大乘积。特别地0 不是正整数1 是最小的正整数0 和 1 都不能拆分因此 dp[0] dp[1] 0。 当 i ≥ 2 时假设对正整数 i 拆分出的第一个正整数是 j1 ≤ j i则有以下两种方案 将 i 拆分成 j 和 i − j 的和且 i − j 不再拆分成多个正整数此时的乘积是 j × (i − j)将 i 拆分成 j 和 i − j 的和且 i − j 继续拆分成多个正整数此时的乘积是 j × dp[i − j]。 因此当 j 固定时有 dp[i] max⁡(j × (i − j), j × dp[i − j])。由于 j 的取值范围是 1 到 i − 1需要遍历所有的 jjj 得到 dp[i] 的最大值因此可以得到状态转移方程如下 dp[i]max⁡1≤ji{max⁡(j×(i−j),j×dp[i−j])}d p[i]\max _{1 \leq ji}\{\max (j \times(i-j), j \times d p[i-j])\} dp[i]1≤jimax​{max(j×(i−j),j×dp[i−j])} 最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后这些正整数的最大乘积。 法二 由于分解成正整数的乘积最大若分解的正整数有1不会使乘积变大所以分解的正整数大于等于2 又至少分解2个正整数当 n 2,或 n 3 时最大的乘积分别为1和2n 4 时分解的最小整数为2否则只会变小 举一些栗子 4 2 2 2 * 2 4 5 2 3 2 * 3 6 6 3 3 3 * 3 9 7 2 2 3 2 5 8 2 3 3 2 6 9 4 2 3 2 7 10 3 3 4 3 7创建数组 dp其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后这些正整数的最大乘积。由以上可知分解的都可表示为 2 或 3 与另一个数 j最大乘积就是2 或 3 乘以另一个数的最大乘积dp[j]. 代码:(Java) 法一 public class IntegerBreak {public static void main(String[] args) {// TODO Auto-generated method stubint n 10;System.out.println(integerBreak(n));}int[] dp new int[n 1];dp[1] 1;for (int i 2; i n; i) {for (int j 1; j i - 1; j) {dp[i] Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));}}return dp[n]; }法二 public class IntegerBreak {public static void main(String[] args) {// TODO Auto-generated method stubint n 10;System.out.println(integerBreak(n));}public static int integerBreak(int n) {if(n / 2 2) {return n - 1;}int[] dp new int[n 1];dp[2] 2;dp[3] 3;for(int i 4; i n; i) {dp[i] Math.max(2*dp[i-2], 3*dp[i-3]);}return dp[n];} }运行结果 复杂度分析 时间复杂度O(n2)O(n^2)O(n2)其中 n 是给定的正整数。对于从 2 到 n 的每一个整数都要计算对应的 dp 值计算一个整数对应的 dp 值需要 O(n) 的时间复杂度因此总时间复杂度是 O(n2)。(法二时间复杂度为O(n)) 空间复杂度O(n)其中 n 是给定的正整数。创建一个数组 dp其长度为 n1 注仅供学习参考 题目来源力扣。
http://www.dnsts.com.cn/news/48670.html

相关文章:

  • wordpress数据库连接时错误企业网站怎么优化
  • 免费不良正能量网站链接网站开发培训 价格
  • 南通建公司网站离职同事以公司名义做网站
  • python做网站原理wordpress改地址错误
  • 怎么做网站点击率监控工具网站推广托管
  • 农药放行单在哪个网站做wordpress搭建电商教程
  • dede如何手机网站和电脑网站的数据同步更新做网站需要知道哪些事情
  • 在建立网站站点的过程中深圳代理记账多少钱一月
  • 查询公司信息去哪里查aso优化什么意思
  • 网站备案一天通过html新闻列表
  • 网站 前台 后台h5响应式网站
  • 同安建设局网站网站建设及网站推广
  • 网站中flash专业做包包的网站
  • 网站域名需要续费的吗身边的网络营销案例
  • 淘宝联盟合作网站api网站建设的实验原理
  • 手机怎样使用域名访问网站wordpress标题title优化代码
  • 专业排名优化网站wordpress后台加载速度慢
  • 自己做网站要会什么软件前端vue低代码开发平台
  • 个人网站介绍模板下载网站建设注意的问题
  • 莉莉卡是哪个网站做的泉州免费网站制作
  • 公司画册设计网站网建公司浅谈网站建设的目的和意义
  • 企业招聘网站模板宁夏建设工程交易中心网站
  • 分类信息系统网站模板线上销售的方法和技巧
  • 湖南火电建设有限公司网站下载应用市场软件
  • 菜单微网站网站建设费用大概多少钱
  • 如何将网站内容做chm软件应用商店下载免费
  • 做移动网站设计网络综合设计实验报告
  • 国外的调查网站上做问卷做ppt医学专业图片网站
  • 山东平台网站建设制作网站规划主要内容
  • 网站建设制作公司 首推万维科技山西营销型网站建设