动态规划 剪绳子问题
给一段长度为n的绳子，请把绳子剪成m段，每段绳子的长度为k[0],k[1],k[2],k[3]....k[m].请问k[0]k[1]k[2].....*k[m]的最大乘积为多少
#include <vector> // 包含vector头文件
#include <algorithm> // 包含algorithm头文件，用于max函数class Solution { // 定义解决方案类
public:int cutRope(int n) { // 主函数，计算最大乘积if (n <= 1) return 0; // 如果绳子长度小于等于1，无法剪断if (n == 2) return 1; // 如果绳子长度为2，最大乘积为1if (n == 3) return 2; // 如果绳子长度为3，最大乘积为2std::vector<int> dp(n + 1, 0); // 创建动态规划数组，初始化为0// 初始化基础情况dp[0] = 0; // 长度为0的绳子乘积为0dp[1] = 1; // 长度为1的绳子乘积为1dp[2] = 2; // 长度为2的绳子乘积为2dp[3] = 3; // 长度为3的绳子乘积为3for (int i = 4; i <= n; i++) { // 从长度4开始计算for (int j = 1; j <= i / 2; j++) { // 尝试所有可能的切割点dp[i] = std::max(dp[i], dp[j] * dp[i - j]); // 更新最大乘积}}return dp[n]; // 返回长度为n的绳子的最大乘积}
};这个实现使用了动态规划的方法来解决问题。以下是主要的设计思路：
- 我们定义了一个
Solution类，其中包含一个cutRope函数来解决这个问题。 - 首先，我们处理了一些特殊情况：
- 如果绳子长度小于等于1，无法剪断，返回0。
- 如果绳子长度为2，最大乘积为1（必须剪断）。
- 如果绳子长度为3，最大乘积为2（必须剪断）。
- 我们创建了一个动态规划数组
dp，其中dp[i]表示长度为i的绳子能得到的最大乘积。 - 初始化基础情况：
dp[0] = 0，dp[1] = 1，dp[2] = 2，dp[3] = 3- 注意，对于长度为2和3的情况，虽然必须剪断，但在作为子问题时，保持完整可能会得到更大的乘积。
- 然后，我们从长度4开始，逐步计算到长度n：
- 对于每个长度i，我们尝试所有可能的切割点j。
- 计算
dp[j] * dp[i-j]，这代表将绳子切割成长度为j和i-j的两段。 - 使用
std::max函数来更新dp[i]，保证它始终是最大的乘积。
- 最后，返回
dp[n]，即为所求的最大乘积。
这个算法的时间复杂度为O(n^2)，空间复杂度为O(n)。
当然可以使用更有效的解法，但是需要一点数学知识这个优化的算法基于一个数学发现：当绳子长度大于3时，尽可能多地切出长度为3的片段会得到最大乘积。如果最后剩下的长度为1，我们应该将其与一个3合并，形成一个长度为4的片段
class Solution { // 定义解决方案类
public:int cutRope(int n) { // 主函数，计算最大乘积if (n <= 3) return n - 1; // 处理特殊情况int quotient = n / 3; // 计算可以切出多少个长度为3的片段int remainder = n % 3; // 计算切完长度为3的片段后剩余的长度if (remainder == 0) { // 如果刚好被3整除return pow(3, quotient); // 返回3的quotient次方} else if (remainder == 1) { // 如果余1return pow(3, quotient - 1) * 4; // 最后的3和1合并为4} else { // 如果余2return pow(3, quotient) * 2; // 最后剩一个2}}private:int pow(int base, int exponent) { // 快速幂函数int result = 1; // 初始化结果为1while (exponent > 0) { // 当指数大于0时循环if (exponent & 1) { // 如果指数的二进制表示中当前位为1result *= base; // 将base乘到结果中}base *= base; // base自乘exponent >>= 1; // 指数右移一位}return result; // 返回结果}
};