【LeetCode】剑指 Offer 14- I. 剪绳子 p96 -- Java Version

news/2024/4/23 15:12:52/文章来源:https://blog.csdn.net/qq_41071754/article/details/129201238

题目链接：https://leetcode.cn/problems/jian-sheng-zi-lcof/

1. 题目介绍（14- I. 剪绳子）

给你一根长度为 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。

【测试用例】：
示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例2：

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

【条件约束】：

提示：

2 <= n <= 58

【相同题目】：

注意：

本题与【LeetCode】No.343. 整数拆分 – Java Version 相同
本题与【LeetCode】剑指 Offer 14- II. 剪绳子 II – Java Version 题目相同，但剪绳子 II 调整了条件约束，变为了 2 <= n <= 1000.

2. 题解

2.1 动态规划 – O(n²)

时间复杂度O(n²)，空间复杂度O(n)

动态规划，自底向上
核心思想：

f(1) = 0
f(2) = 1
f(3) = 2
……
f(n) = max(f(i) * f(n-i))

求解的核心问题：求出长度为n的绳子，剪成整数长度的 m 段所能得到的最大乘积；
分解成子问题：想要求出f(n)，就要先求f(i) * f(n-i)，并找出所有可能的最大值。

class Solution {// 方法一：动态规划public int cuttingRope(int n) {// 错误判断：确保长度在正确的范围内if (n < 2) return 0;if (n == 2) return 1;if (n == 3) return 2;// 定义数组int[] result = new int[n+1];// result数组是用来存储子问题的最优解，但是下面三个不是，而是数字本身result[1] = 1;result[2] = 2;result[3] = 3;int max = 0;// 循环求解，遍历每一种可能，并将最大值存入数组for (int i = 4; i <= n; i++){// 这里让j <= i/2是为了避免重复计算for (int j = 1; j <= i/2; j++){result[i] = result[j] * result[i-j];// 比较得出最大值if (result[i] > max) max = result[i];}// 把最大值存入数组result[i] = max;}return result[n];}
}

在这里插入图片描述

2.2 贪婪算法

时间复杂度O(1)，空间复杂度O(1)

dp[2]= 1 = 1*1;
dp[3]= 2 = 1*2;
dp[4]= 4 = 2*2;
dp[5]= 6 = 2*3;
dp[6]= 9 = 3*3;
dp[7]= 12 = 2*2*3;
dp[8]= 18 = 2*3*3;
dp[9]= 27 = 3*3*3;
dp[10]= 36 = 2*2*3*3;
…
经过观察，可以得出最优分解必定是包含了2或者3的结论，也就是说只需要考虑这两种情况，就可以得出最优解！可以用数学方式来证明贪婪算法的正确性。

当 n>= 5时，我们尽可能多地剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。

class Solution {// 方法一：贪心算法public int cuttingRope(int n) {// 1. 错误判断：确保长度在正确的范围内if (n <= 3) return n-1;// 2. 看看n长度的绳子能够被剪出几根长度为3的绳子int timeOf3 = n/3;// 3. 当绳子最后剩下的长度为4时，把绳子剪成两段长度为2的绳子if (n - 3 * timeOf3 == 1) timeOf3--;int timeOf2 = (n- 3 * timeOf3)/2;// 4. 最后返回结果return (int)(Math.pow(3,timeOf3)) * (int)(Math.pow(2,timeOf2));}
}