剑指Offer： 剪绳子（Python语言实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指Offer： 剪绳子（Python语言实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含925字，纯文字阅读大概需要2分钟。

内容图文

给你一根长度为n的绳子，请把绳子剪成m段(m、n都是整数, n>1并且m>1)，每段绳子的长度记为k[0],k[1],...,k[m]。
请问k[0]*k[1]*...*k[m]可能的最大乘积是多少？

运用动态规划解决问题的关键是具备从上到下分析问题、从下到上解决问题的能力。

def max_product_after_cutting(n):
    if n < 2:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 2
    res = [0, 1, 2, 3]
    for ni in range(4, n+1):
        max_value = 0
        for nj in range(1, ni//2 + 1):
            current = res[nj] * res[ni-nj]
            if current > max_value:
                max_value = current
            else:
                break
        res.append(max_value)
    return res[-1]

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

def max_product_after_cutting(n):
    if n < 2:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 2

    three = n // 3
    if n - three*3 == 1:
        three -= 1
    two = (n - three*3) // 2

    return pow(2, two) * pow(3, three)

把一个具体的场景抽象成一个能够用动态规划或者贪婪算法解决的模型，而灵活运用贪婪算法则需要扎实的数学基本功。

（最近更新：2019年07月10日）

内容总结

以上是互联网集市为您收集整理的剑指Offer： 剪绳子（Python语言实现）全部内容，希望文章能够帮你解决剑指Offer： 剪绳子（Python语言实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端