网页设计网站免登陆_成都小程序开发公司_怎么做好市场宣传和推广_搜狗站长工具综合查询

1.砍竹子I 

        需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。        

        现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。

示例 1：

输入: bamboo_len = 12 输出: 81

提示：

2 <= bamboo_len <= 58

1.1动态规划

        这道题给定一个大于 1 的正整数 bamboo_len，要求将 bamboo_len 拆分成至少两个正整数的和，并使这些正整数的乘积最大化，返回最大乘积。

        令 x 是拆分出的第一个正整数，则剩下的部分是 bamboo_len−x，bamboo_len−x 可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。

        创建数组 dp，其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 dp[0]=dp[1]=0。

        当 i≥2 时，假设对正整数 i 拆分出的第一个正整数是 j（1≤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，需要遍历所有的 j 得到 dp[i] 的最大值。

        时间复杂度：O(bamboo_len 2)，其中 bamboo_len 是给定的正整数。对于从 2 到 bamboo 
_len 的每一个整数都要计算对应的 dp 值，计算一个整数对应的 dp 值需要 O(bamboo_len) 的时间复杂度，因此总时间复杂度是 O(bamboo_len2 )。空间复杂度：O(bamboo_len)，其中bamboo_len 是给定的正整数。创建一个数组 dp，其长度为 bamboo_len+1。

代码实现：

class Solution {public int cuttingRope(int bamboo_len) {
//创建长度为bamboo_len + 1的数组，索引可到bamboo_len。int[] dp = new int[bamboo_len + 1];
//从1开始遍历到所需长度。for (int i = 1; i <= bamboo_len; i++) {
//用于保存每个的极大值。int curMax = 0;
//分割从1到i-1for (int j = 1; j < i; j++) {
//记录最大值curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));}dp[i] = curMax;}
//返回值return dp[bamboo_len];}
}

1.2 优化动态规划

        如果 j≥4，则 dp[j]≥j，当且仅当 j=4 时等号成立，即当 j≥4 时一定能将 j 拆成至少两个正整数的和，这些正整数的乘积大于或等于 j。同时也可以得到，如果 j≥4，则 dp[i]≥j×dp[i−j]，只有当 j=4 时等号可能成立。

        如果取 j=1，则有 dp[i]≥1×dp[i−1]=dp[i−1]。当 i≥3 时，dp[i−1] 是将正整数 i−1 拆分成至少两个正整数的和之后，这些正整数的最大乘积，在拆分成的正整数中，任选一个数字加 1，则拆分成的正整数的和变成 i，且乘积一定大于 dp[i−1]，因此必有 dp[i]>dp[i−1]，即当 j=1 时不可能得到最大的 dp[i] 的值。根据上述分析可知，计算 dp[i] 的值只需要考虑 j=2 和 j=3 的情况，不需要遍历从 1 到 i−1 的所有值。

        其次考虑 j×(i−j) 这一项。根据上述推导可知，如果 j≥4，则 dp[j]≥j，当且仅当 j=4 时等号成立。因此在 i−j≥4 的情况下，有 dp[i−j]≥i−j，dp[i]≥j×dp[i−j]≥j×(i−j)，此时计算 dp[i] 的值不需要考虑 j×(i−j) 的值。如果 i−j<4，在计算 dp[i] 的值的时候就需要考虑 j×(i−j) 的值。在考虑 j×dp[i−j] 时，根据上述分析，只需要考虑 j=2 和 j=3 的情况。在考虑 j×(i−j) 时，需要考虑 j 的哪些值？如果 j=1，则 1×(i−1)=i−1，当 i=2 或 i=3 时有 dp[i]=i−1，当 i≥4 时有 dp[i]≥i>i−1，显然当 i≥4 时取 j=1 不可能得到最大乘积，因此 j=1 时是不需要考虑的。如果 j≥4，dp[i] 是否可能等于 j×(i−j)？当 i 固定时，要使得 j×(i−j) 的值最大，j 的值应该取 j=i/2，这里的 / 表示整数除法。当 j≥4 时，若要满足 j=i/2，则 i≥8，此时 i−j≥4，利用上述结论，dp[i−j]≥i−j，因此 j×dp[i−j]≥j×(i−j)。由此可见，当 j≥4 时，计算 dp[i] 只需要考虑 j×dp[i−j]，不需要考虑 j×(i−j)。又由于在使用 j×dp[i−j] 计算 dp[i] 时，j=2 和 j=3 的情况一定优于 j≥4 的情况，因此无论是考虑 j×dp[i−j] 还是考虑 j×(i−j)，都只需要考虑 j=2 和 j=3 的情况。

        时间复杂度：O(bamboo_len)，其中 bamboo_len 是给定的正整数。和方法一相比，计算每个整数对应的 dp 的值的时间复杂度降到 O(1)，因此总时间复杂度降到 O(bamboo_len)。空间复杂度：O(bamboo_len)，其中 bamboo_len 是给定的正整数。创建一个数组 dp，其长度为 bamboo_len+1。

代码实现：

class Solution {public int cuttingRope(int bamboo_len) {
//如果长度小于等于3if (bamboo_len <= 3) {
//直接返回长度减1，1对应0，2对应1，3对应2。return bamboo_len - 1;}int[] dp = new int[bamboo_len + 1];dp[2] = 1;
//自3开始分割。for (int i = 3; i <= bamboo_len; i++) {
//只需考虑分割2和分割3。dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));}return dp[bamboo_len];}
}

1.3数学方法

        方法二中利用了数学知识降低时间复杂度。正整数 4 可以拆分成 2+2，乘积不变（4=2×2）。对于大于 4 的正整数，总是存在一种拆分的方案，使得拆分成的两个正整数的乘积大于拆分前的正整数（例如，5=2+3，2×3=6>5）。

根据 bamboo_len 除以 3 的余数进行分类讨论：

        如果余数为 0，即 bamboo_len=3m(m≥2)，则将 bamboo_len 拆分成 m 个 3；

        如果余数为 1，即 bamboo_len=3m+1(m≥1)，由于 2×2>3×1，因此将 bamboo_len 拆分成 m−1 个 3 和 2 个 2；

        如果余数为 2，即 bamboo_len=3m+2(m≥1)，则将 bamboo_len 拆分成 m 个 3 和 1 个 2。

上述拆分的适用条件是 bamboo_len≥4。如果 bamboo_len≤3，则上述拆分不适用，需要单独处理。

        如果 bamboo_len=2，则唯一的拆分方案是 2=1+1，最大乘积是 1×1=1；

        如果 bamboo_len=3，则拆分方案有 3=1+2=1+1+1，最大乘积对应方案 3=1+2，最大乘积是 1×2=2。

这两种情形可以合并为：当 bamboo_len≤3 时，最大乘积是 bamboo_len−1。

归纳证明法

第一步：证明最优的拆分方案中不会出现大于 4 的整数。

        假设出现了大于 4 的整数 x，由于 2(x−2)>x 在 x>4 时恒成立，将 x 拆分成 2 和 x−2 可以增大乘积。因此最优的拆分方案中不会出现大于 4 的整数。

第二步：证明最优的拆分方案中可以不出现整数 4。

        如果出现了整数 4，我们可以用 2×2 代替之，乘积不变。

        此时，我们可以知道，最优的拆分方案中只会出现 1，2 和 3。

第三步：证明当 bamboo_len≥5 时，最优的拆分方案中不会出现整数 1。

        当 bamboo_len≥5 时，如果出现了整数 1，那么拆分中剩余的数的和为 bamboo_len−1≥4，对应这至少两个整数。我们将其中任意一个整数 x 加上 1，乘积就会增大。因此最优的拆分方案中不会出现整数 1。

        此时，我们可以知道，当 bamboo_len≥5 时，最优的拆分方案中只会出现 2 和 3。

第四步：证明当 bamboo_len≥5 时，最优的拆分方案中 2 的个数不会超过 3 个。

        如果出现了超过 3 个 2，那么将它们转换成 2 个 3，可以增大乘积，即 3×3>2×2×2。

        此时，bamboo_len≥5 的最优拆分方案就唯一了。这是因为当最优的拆分方案中 2 的个数分别为 0，1，2 个时，就对应着 bamboo_len 除以 3 的余数分别为 0，2，1 的情况。因此我们可以得到和「函数极值证明法」相同的分类讨论结果。

        当 bamboo_len=4 时，4=2×2 的最优拆分方案也可以放入分类讨论结果；当 2≤bamboo_len≤3 时，只有唯一的拆分方案 1×(bamboo_len−1)。

        时间复杂度：O(1)。涉及到的操作包括计算商和余数，以及幂次运算，时间复杂度都是常数。空间复杂度：O(1)。只需要使用常数复杂度的额外空间。

代码实现：

class Solution {public int cuttingRope(int bamboo_len) {
//若小于3，直接返回长度减1。if (bamboo_len <= 3) {return bamboo_len - 1;}
//本质上就是分割3.int quotient = bamboo_len / 3;int remainder = bamboo_len % 3;
//最好情况全部分为3。
//若剩2，则分割出一个2。
//若剩余1，则拿出一个3，分割为2+2。if (remainder == 0) {return (int) Math.pow(3, quotient);} else if (remainder == 1) {return (int) Math.pow(3, quotient - 1) * 4;} else {return (int) Math.pow(3, quotient) * 2;}}
}

1.4总结

        本题属于动态规划类题目，在动态规划的基础上可以实现进一步优化其时间复杂度和空间复杂度。但本质问题仍是数学，最优解法也是从数学推论的角度上展开，难怪会说，学好了数学会鄙视其他一切学科（bushi）。II

2.砍竹子II

        现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为 正整数。请返回每段竹子长度的 最大乘积 是多少。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：bamboo_len = 12 输出：81

提示：

• 2 <= bamboo_len <= 1000

解题思路：
切分规则的推导流程请见上一题「砍竹子 I」。

切分规则：
最优： 3 。把竹子尽可能切为多个长度为 3 的片段，留下的最后一段竹子的长度可能为 0,1,2 三种情况。
次优： 2 。若最后一段竹子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1 。若最后一段竹子长度为 1 ；则应把一份 3+1 替换为 2+2，因为 2×2>3×1。

        在大数计算中，大数越界问题通常发生在进行乘法、幂运算等操作时，由于结果超出了数据类型能表示的范围。以Java为例，int 类型能表示的范围在 [-2^31, 2^31-1] 之间，而 long 的范围则是 [-2^63, 2^63-1]。当计算结果超出这些范围时，就会出现大数越界问题。

2.1大数求余问题

1. 大数乘法导致越界问题

   • 当两个大数相乘时，结果可能超出 long 或 int 类型的最大表示范围。

2. 大数的幂运算导致越界

   • 幂运算通常会迅速产生极大的数字，容易超出数据类型的限制。

为了解决这些问题，通常我们可以通过 求余操作 来控制结果的范围。由于很多问题只关心计算结果对某个数的余数，因此我们可以在每次操作之后都取模，保证结果不越界。

2.2常见解决方案

2.2.1循环求余

在处理大数乘法时，最简单的办法是逐步将结果求余，避免数值的增长超出限制。时间复杂度 O(N) ： 其中 N=a ，即循环的线性复杂度。

原理： 假设你需要计算 a * b % mod，你可以通过以下步骤来避免大数越界：

• 先将 a 和 b 都对 mod 取余，得到 a' = a % mod 和 b' = b % mod。
• 然后计算 a' * b'，并在每一步都对 mod 取余。

应用场景： 在连续进行乘法或累乘时，每次都将中间结果对 mod 取余，可以有效防止大数越界。例如，在处理大数阶乘、连乘问题时。

2.2.2 快速幂求余（快速幂算法）

快速幂算法是一种用于高效计算大数幂取模的方法。它可以将时间复杂度从 O(n) 降到 O(log n)。

原理： 快速幂利用了幂的性质：

• 如果 n 是偶数，那么 a^n = (a^(n/2))^2。
• 如果 n 是奇数，那么 a^n = a * a^(n-1)。

在每一步计算时，我们都可以对结果取模，从而避免大数越界问题。具体的思路是将 n 分解为二进制形式，通过重复平方的方式，快速计算大数幂。

步骤：

1. 初始化 res = 1，这是最后的结果。
2. 当 n > 0 时：
   • 如果 n 是奇数，更新结果 res = (res * a) % mod。
   • 将 a = (a * a) % mod，并将 n 减半（n = n / 2）。
3. 返回 res，这是 a^n % mod 的值。

应用场景： 当需要计算大数的幂取模时，快速幂是一种非常有效的算法。例如，在密码学中，经常需要计算 a^b % c，快速幂能够极大提高效率并避免大数越界。

2.3举例说明

假设我们有这样一个问题：计算 (a^b) % mod，其中 a、b 和 mod 都是很大的数。直接计算 a^b 可能会导致大数越界，这时候快速幂求余算法能够派上用场。

• 比如计算 3^100000 % 1000000007，如果直接计算 3^100000，结果会非常大，远远超过 long 的范围。
• 使用快速幂算法，可以通过逐步对 mod 取余，避免大数溢出问题，并快速得出结果。

2.4总结

• 循环求余 适合连续的乘法问题，在每次操作后立即取模，避免数值增长过快。
• 快速幂求余 通过利用幂的性质，以 O(log n) 的复杂度快速计算大数幂，并通过每一步取模避免大数溢出。

        两者都可以解决大数越界问题，并在Java中广泛应用于需要大数计算的场景，比如密码学和算法竞赛问题中。

代码实现：

class Solution {public int cuttingBamboo(int bamboo_len) {if(bamboo_len <= 3) return bamboo_len - 1;int b = bamboo_len % 3, p = 1000000007;
//快速求余数long rem = 1, x = 3;for(int a = bamboo_len / 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);}
}