动态规划是编程面试中的热门话题。一般来说,能够用动态规划求解的问题具有如下三个特点:
由于子问题在分解大问题的过程中重复出现,为了避免重复求解子问题,我们可以用从下往上的顺序先计算小问题的最优解并存储下来,再以此为基础求取大问题的最优解。简单来说就是「从上往下分析问题,从下往上求解问题」。
与动态规划不一样,当应用贪婪算法解决问题时,每一步都可以做出一个贪婪的选择,基于这个选择,我们确定能够得到最优解。关于贪婪算法的正确性需要依赖于数学证明。
❝题目:给你一根长度为
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。 ❞
「示例」
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
限制:
2 <= n <= 58
我们首先尝试用「动态规划」方法解决这个问题。定义
为把长度为
的绳子剪成若干段后各段长度乘积的最大值,则我们可以将该问题分解为如下子问题:
其中
。这是一个自上到下的递归公式,其中包含很多重复的子问题。为了避免大量不必要的计算。我们可以自下而上计算,将每个
存储起来,直到得到
。
需要注意的是,由于题目要求绳子必须要剪,所以对于
的情况需要单独讨论,因为其不剪的状态下得到的乘积要大于剪后的任意组合的乘积(实际上这一阈值的选择需要数学证明)。
本方法的 java 实现如下:
class Solution {
public int cuttingRope(int n) {
if (n <= 3) return n - 1; // 处理特殊情况
int dp[] = new int[n + 1]; // 数组存储 1-n 下的最优解
dp[1] = 1;
dp[2] = 2;
dp[3] = 3; // 注意前 3 个的值并不是输出结果
for (int i = 4; i <= n; i++) { // 从 4 开始
int max = 0;
for (int j = 1; j <= i/2; j++) { // 由于乘法交换律,j 只要遍历一半即可
max = Math.max(max, dp[j] * dp[i - j]);
}
dp[i] = max;
}
return dp[n];
}
}
易知该方法的「时间复杂度」为
,「空间复杂度」为
。
这道题还可以使用「贪婪算法」解决。我们需要用数学方法找出「优先级最高的切分长度」。首先,基于均值不等式可以得到:
即将绳子分为
段时,当且仅当
时等号成立,即乘积最大。假设这一等分的长度为
,即
,则乘积为
。由于
为常数,因此我们有:
我们只需要求出
的极大值即可,对其求导数可得到:
因此当取得极值时
,易知此为极大值点。
由于切分长度必须为整数,所以取
或
,经验证:
因此
时,乘积最大。
而实际上,不可能所有的长度都能被 3 整除,但是尽可能的以 3 将绳子分割可以逼近理想中的最大值。因此,我们使用如下的贪婪算法:
时,按题目要求必须切分,因此返回
;
时,把绳子尽可能地切为多个长度为 3 的片段,如果最后一段长度为 2,则保留,如果最后一段长度为 1,则把一份
替换为
,因为
。
基于上述方法的 python 实现如下:
class Solution:
def cuttingRope(self, n: int) -> int:
if n <= 3: return n - 1
a, b = n // 3, 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)
该方法的时间复杂度和空间复杂度均为
。注意:python 中 math.pow()
的求幂时间复杂度为
,*
和 pow()
的时间复杂度为
。
此外,LeetCode 上还给出了此题的变式,添加了「大数越界情况下的求余问题」。答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,需返回 1。这种情况下如果采用动态规划算法,可能会导致超时,因此考虑使用贪婪算法。
在求余操作时需要注意,不能在最后一步再取余,因为最后的值可能已经超出范围,而应该在贪婪算法的每一步中进行求余,以保证不会越界。这里使用了「快速幂求余」算法,其时间复杂度为对数级别。这里对快速幂求余的原理进行简单的说明,首先给出两条求余相关的定理:
基于上述两条定理,对于
,我们可以推导出:
因此,我们可以通过「循环」将幂不断地减小直到变成 1,而底数则一直用原底数的平方求余替换即可。通过这种方法,我们可以得到较低的时间复杂度(二分),同时保证不会越界。快速幂求余的单独 java 实现如下:
int PowerMod(int a, int b, int c)
{
int ans = 1;
a = a % c; // 一般情况下先求一次余,不影响结果
while (b > 0) {
if (b % 2 == 1) ans = (ans * a) % c; // 最后一定会有一次奇数,也可以使用位运算 b & 1
b /= 2; // 每次将 b 二分缩小,也可以使用位运算 b >>= 1
a = (a * a) % c; // 不论奇偶都要更新
}
return ans;
}
上述实现中,当 b 为奇数时,需要额外地乘上
,再循环下去,注意这里 ans 的初始值为 1,即在整个循环过程中 ans 只累积奇数情况下多出的部分,只有当
时,才会将最终得到的底数计入(这里不太好理解,我想了很久才明白)。
基于快速幂求余,我们可以得到本题的解法:
class Solution {
public int cuttingRope(int n) {
if(n <= 3) return n - 1;
int b = n % 3, p = 1000000007;
long rem = 1, x = 3; // 使用 long 类型防止越界
for (int a = n / 3 - 1; a > 0; a /= 2) { // 留一个 3 最后处理
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);
}
}
该方法的空间复杂度为
,时间复杂度与快速幂求余的复杂度相关,为
。