网站建设时间计划表,广州口碑好的网站建设定制,1688货源网一件代发拼多多,怎样在安装wordpress摘要
剑指 Offer 14- I. 剪绳子 剑指 Offer 14- II. 剪绳子 II 343. 整数拆分
一、动态规划解析
这道题给定一个大于1的正整数n#xff0c;要求将n 拆分成至少两个正整数的和#xff0c;并使这些正整数的乘积最大化#xff0c;返回最大乘积。令x是拆分出的第…摘要
剑指 Offer 14- I. 剪绳子 剑指 Offer 14- II. 剪绳子 II 343. 整数拆分
一、动态规划解析
这道题给定一个大于1的正整数n要求将n 拆分成至少两个正整数的和并使这些正整数的乘积最大化返回最大乘积。令x是拆分出的第一个正整数则剩下的部分是 n−xn−x可以不继续拆分或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积因此可以使用动态规划求解。
创建数组dp其中dp[i]表示将正整数i拆分成至少两个正整数的和之后这些正整数的最大乘积。特别地0不是正整数1是最小的正整数0和1都不能拆分因此 dp[0]dp[1]0。
当 i≥2时假设对正整数i拆分出的第一个正整数是 j(1≤ji则有以下两种方案
将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需要遍历所有的j得到dp[i]的最大值因此可以得到状态转移方程如下dp[i]max(1≤ji){max(j×(i−j),j×dp[i−j])}。最终得到dp[n]的值即为将正整数n拆分成至少两个正整数的和之后这些正整数的最大乘积。
package DP;/*** Classname JZ14* Description TODO* Date 2023/3/1 21:34* Created by xjl*/
public class JZ14剪绳子 {public int cuttingRope(int n) {// 定义dp的数组 dp[0]dp[1]0int[] dp new int[n 1];for (int i 2; i n; i) {int curMax 0;for (int j 1; j i; j) {curMax Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));}dp[i] curMax;}return dp[n];}
}复杂度分析
时间复杂度O(n^2)其中n是给定的正整数。对于从2到n的每一个整数都要计算对应的dp 值计算一个整数对应的 dp值需要O(n)的时间复杂度因此总时间复杂度是O(n^2)。空间复杂度O(n)其中n是给定的正整数。创建一个数组dp其长度为 n1
二、数学方法实现
设将长度为n的绳子切为a段nn1n2...na题等价于求解max(n1×n2×...×na)以下公式为“算术几何均值不等式” 等号当且仅当n1n2...na时成立。 算法流程
当n≤3时按照规则应不切分但由于题目要求必须剪成m1段因此必须剪出一段长度为1的绳子即返回 n−1。当n3时求n除以3的 整数部分a和余数部分b 即n3ab并分为以下三种情况 当 b0时直接返回3a 当 b1时要将一个 13转换为 22因此返回 3a−1×4 当 b2时返回 3a×2。class Solution {public int cuttingRope(int n) {if(n 3) return n - 1;int a n / 3, b n % 3;if(b 0) return (int)Math.pow(3, a);if(b 1) return (int)Math.pow(3, a - 1) * 4;return (int)Math.pow(3, a) * 2;}
}
三、大数越界情况下的求余问题
此题与剪绳子主体等价唯一不同在于本题目涉及 “大数越界情况下的求余问题” 。 切分规则
最优3。把绳子尽可能切为多个长度为3的片段最后一段绳子长度可能为0,1,2三种情况。次优2。若最后一段绳子长度为2 则保留不再拆为 11 。最差1。若最后一段绳子长度为1 则应把一份31替换为 22因为 2×23×1。
算法流程
当n≤3时按照规则应不切分但由于题目要求必须剪成m1段因此必须剪出一段长度为1的绳子即返回n−1。
当n3时求n除以 3的整数部分a和余数部分b 即 n3ab 并分为以下三种情况设求余操作符号为 ⊙
当 b0时直接返回 3a⊙1000000007当 b1时要将一个 13转换为 22因此返回 (3a−1×4)⊙1000000007当 b2时返回 (3a×2)⊙1000000007。大数求余解法
大数越界当a增大时最后返回的3a大小以指数级别增长可能超出int32 甚至int64 的取值范围导致返回值错误。大数求余问题 在仅使用int32 类型存储的前提下正确计算xa对p求余即 xa⊙p的值。解决方案 循环求余、快速幂求余 其中后者的时间复杂度更低两种方法均基于以下求余运算规则推出(xy)⊙p[(x⊙p)(y⊙p)]⊙p
class Solution {public int cuttingRope(int n) {if(n 3) return n - 1;int b n % 3, p 1000000007;long rem 1, x 3;for(int a n / 3 - 1; a 0; a / 2) {if(a % 2 1) rem (rem * x) % p;x (x * x) % p;}if(b 0) return (int)(rem * 3 % p);if(b 1) return (int)(rem * 4 % p);return (int)(rem * 6 % p);}
}
博文参考
《leetcode》
