剪绳子
解题思路：
-
对于长度为 n 的绳子，当 n ≥ 2 时，可以剪成至少两个绳子；
- 令 k 是剪出的第一段绳子，则剩下的部分是 n−k；
- n−k 可以不继续剪，或者继续剪成至少两段绳子（一个问题可以分解为相似的子问题因此想到动态规划）；
-
确定 dp 数组以及下标的含义：dp[i] 表示将长度为 i 的绳子剪成至少两段绳子之后，这些绳子长度的最大乘积；
-
确定状态转移方程：
- 当 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，需要遍历所有的 j 得到 dp[i]；
- 当 i ≥ 2 时，假设对长度为 i 绳子剪出的第一段绳子长度是 j（1 ≤ j < i），则有以下两种方案：
-
初始化状态：初始化 dp[2] = 1；
复杂度：
-
时间复杂度：O(n^2)，其中 n 是给定的正整数，对于从 2 到 n 的每一个整数都要计算对应的 dp 值，计算一个整数对应的 dp 值需要 O(n) 的时间复杂度，因此总时间复杂度是 O(n^2)；
-
空间复杂度：O(n)，其中 n 是给定的正整数，创建一个数组 dp，其长度为 n+1；
代码实现：
function cuttingRope(n: number): number {
// 定义 dp 数组
let dp = new Array(n + 1).fill(0);
// 初始化
dp[2] = 1;
for (let i = 3; i <= n; i++) {
// j 遍历到小于 i 的值
for (let j = 1; j < i - 1; j++) {
// dp[i] 表示将长度为 i 的绳子剪成至少两段绳子之后，这些绳子长度的最大乘积
dp[i] = Math.max(dp[i], (i - j) * j, dp[i - j] * j);
}
}
return dp[n];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
vue2.x✍️ 生命周期
上一篇
评论
