每日一道算法之--剪绳子

动态规划数学贪心算法

Word count: 851Reading time: 3 min

 2020/03/12   Share

剪绳子

力扣面试题14- I :https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
相同题目:343. 整数拆分

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m] 。请问 k[0]k[1]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是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

1. 动态规划

一看到这道题的时候,看到最这个字,首先我第一肯定是想到动态规划。当我们首先要判断边界，当n小于4的时候，只会有一种可能或者没有，如 n == 2时,只可能分成两段,分别为1, 1。当n大于3时，我们剪断绳子的第一刀时，可以剪1,2，.., n-1的长度,即有n-1中可能所以状态转移方程为

f(n) = max(f(i) * f(n - i)) , 其中 0<i<n

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n < 2: return 0
        if n == 2: return 1
        if n == 3: return 2
        dp = ['' for _ in range(n + 1)]
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        max_count = 0
        for i in range(4, n + 1):
            # 只需要遍历到一半,因为前半部分和后半部分是一样的
            for j in range(1, i //2 + 1):
                max_count = max(max_count, dp[j] * dp[i - j])
                dp[i] = max_count
        return dp[n]

1.1 复杂度分析

时间复杂度:当n > 4时,每一个子问题(假设长度为m),他的第一刀都有m - 1中可能,所以需要两层循环,时间复杂度为$$O(n^2)$$

空间复杂度:运用了列表的数据结构,且其大小和n有关,即空间复杂度为O(1)

2. 贪婪算法

通过复杂度分析,动态规划的时间复杂度和空间复杂度都不太理想,所以我有翻了《剑指offer》里看了一种非常巧妙的方法—-贪婪算法

可以发现,只有当n == 4时,以2分割比3更佳
所以当绳子大于4时,尽可能地以3分割;如果剩下的绳子刚好等于4,则将4分割成两个2

import math
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <=  3: return n - 1
        count3 = n // 3
        # 如果存在4,要以2分割
        if n - 3 * count3 == 1:
            count3 -= 1
        count2 = (n - count3 * 3) // 2
        return int(math.pow(3, count3)* math.pow(2, count2))

2.1 复杂度分析

时间复杂度: O(1)

空间复杂度:O(1)

总结

做这道题之前,我只要看到最这个字,肯定都会联想到动态规划,做了这道题之后,哎,每一种题目,都还是会有自己特定的最合适的算法,而不是dp永远都是最好的.向之前有一道题322. 零钱兑换,我一开始就是想到了贪心算法,但其实正确的解法是动态规划。而且也要动脑子,这道题其实和数学的联系很大,如果理解了规律真的不难,还是要多刷多练,踏实地学习.

类似题目

171. Excel表列序号

975. 奇偶跳

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/03/12/algorithm-interview-14/

发表日期：March 12th 2020, 11:58:33 pm

更新日期：March 13th 2020, 12:00:21 am

Next Post

学习笔记之---堆和栈的区别
Previous Post

每日一道算法之--寻找旋转排序数组中的最小值

CATALOG

1. 剪绳子

