题解 | #剪绳子#
剪绳子
https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8
解题思路
可以线从简单的情况进行分析:
- 当绳子长度为2和3的时候,不切分的乘积是最大的;当绳子长度为4的时候,对半切分的乘积是最大的。
- 而继续往后计算的话,有一个规律:假设一段长为i的绳子,其后j段不能切分,那么我们知道它前面i-j长的绳子切分乘积最大值,则我们可以知道最终的乘积,一个一个去比较大小,取大值。
复杂度
- 时间复杂度为O(N);
- 空间复杂度为O(N)。
代码
Python
class Solution: def cutRope(self , n: int) -> int: # write code here if n < 4: return n dp = [0 for _ in range(n+1)] dp[1] = 1 dp[2] = 2 dp[3] = 3 dp[4] = 4 for i in range(5, n+1): for j in range(1, i): dp[i] = max(dp[i], j*dp[i-j]) return dp[-1]
C++
class Solution { public: int cutRope(int n) { // write code here if(n<4) { return n; } vector<int> dp(n+1, 0); dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 4; for(int i = 5; i < n+1; i++) { for(int j = 1; j < i; j++) { dp[i] = max(dp[i], j*dp[i-j]); } } return dp[n]; } };