【动态规划、贪心】剪绳子

风吹夏天 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)

相关推荐