VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > Python基础教程 >
  • python基础教程之【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.

解题思路:动态规划

#面试题14:剪绳子
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))

竟然大概看懂(人家的代码)了……安不里屋包


相关教程