风吹夏天 2020-01-02
给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少?
例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
输入描述:
输入一个数n,意义见题面。(2 <= n <= 60)
示例1
输入 8 输出 18
示例2
输入 4 输出 4
1,动态规划,从上往下分析问题,从下往上求解;Time: O(N^2),Space: O(N)
2,贪心,先尽可能剪多个3,再剪2。Time: O(1),Space: O(1)
为什么这么剪可以得到最优解?需要用数学公式来证明这是正确的。。。(好吧,这个解释不足以让我信服,但书上就是这么写的啊啊,,按这个推理出来也是对的,,,那就记住吧!书上还说运用贪心算法需要扎实的数学基本功..)
代码实现:
# class Solution: # # 动态规划算法,从上往下分析问题,从下往上求解 # # Time: O(N^2), Space: O(N) # def cutRope(self, number): # n = number # # # 计算好前两个直接返回 # if n == 2: # return 1 # if n == 3: # return 2 # # f = [0 for _ in range(n+1)] # f[1] = 1 # f[2] = 2 # 此处的f(1, 2, 3)均为初始操作,为之后 i>4 的计算做准备,不代表实际的f(i) # f[3] = 3 # # # f(i) = max( f(j)*f(i-j) ),即f(i)有多种切割方法,取乘积最大的。f数组保存n>4时剪绳子的最优解 # # 例如f(5) = max( f(1)*f(4), f(2)*f(3) ) # # 例如f(6) = max( f(1)*f(5), f(2)*f(4), f(3)*f(3) ) # for i in range(4, n+1): # 从下往上求解 # max = 0 # for j in range(1, i//2+1): # 求最大的切割方式 # if f[j]*f[i-j] > max: # max = f[j]*f[i-j] # f[i] = max # # # print(f) # return f[n] class Solution: # 贪心算法,每一步都做出贪婪的选择,最终结果也是最优的。 # 先尽可能剪多个3,再剪2。为什么这么剪可以得到最优解?需要用数学公式来证明这是正确的。。。 # Time: O(1), Space: O(1) def cutRope(self, number): if number == 2: return 1 if number == 3: return 2 n = number number3 = n//3 # 可以剪出3的个数 if n - number3*3 == 1: # 如果最后剩下的长度为4,不能再剪长度为1*3,而应该是2*2 number3 -= 1 number2 = (n - number3*3)//2 # 剪完 3 之后剩下的长度剪2 ans = pow(3, number3) * pow(2, number2) # 多少个3 多少个2 return ans s = Solution() ans = s.cutRope(8) print(ans)