Python语言之详解剑指offer 14：剪绳子-职坐标

Python语言之详解剑指offer 14：剪绳子

从安 2019-06-12 来源：阅读 1452 评论 0

摘要：本篇文章主要讲述Python语言之详解剑指offer 14：剪绳子，希望阅读本篇文章以后大家有所收获，帮助大家对相关内容的理解更加深入。

本篇文章主要讲述Python语言之详解剑指offer 14：剪绳子，希望阅读本篇文章以后大家有所收获，帮助大家对相关内容的理解更加深入。

Python语言之详解剑指offer 14：剪绳子

题目：给你一根长度为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.

解题思路：动态规划

剪绳子class Solution:

 def dynamic_programming(self, n):
        if n < 2:   #长度<2，为0
            return 0
        if n == 2:  #长度=2，剪成两段1
            return 1
        if n == 3:  #长度=3,1x2
            return 2
        tmp_lst = [0, 1, 2, 3]
        for i in range(4, n+1):     #长度>4
            max = 0
            for j in range(1, i):   #从下往上分析问题
                tmp = tmp_lst[j] * tmp_lst[i - j]
                if max < tmp:
                    max = tmp
            tmp_lst.append(max)
        return tmp_lst[n]
 
s = Solution()
print(s.dynamic_programming(8))

本文由职坐标整理发布，学习更多的相关知识，请关注职坐标IT知识库！

编程语言python python编程实战 python编程100例

本文由 @从安发布于职坐标。未经许可，禁止转载。