剣指offer-14.ロープを切るダイナミックプランニング、貪欲アルゴリズム-python

#-*- coding:utf-8 -*-
'''
description:
 name：   
   ：       n   ，      m (n>1,m>1)，         k[0],k[1]....k[m],  k[0]*k[1]*..*k[m]          
'''


class Solution:
    def dynamic_programming(self, n):
        if n < 2:
            return 0
        if n == 2:
            return 1
        if n == 3:
            return 2
        tmp_lst = [0, 1, 2, 3]

        for i in range(4, n+1):
            max = 0
            for j in range(1, i//2+1):
                tmp = tmp_lst[j] * tmp_lst[i-j]
                if max < tmp:
                    max = tmp
            tmp_lst.append(max)
        return tmp_lst[n]

    '''
           n<=3                    ，  n>3                  
          n                4   
    '''
    def greedy_algorithm(self, n):
        if n < 2:
            return 0
        if n == 2:
            return 1
        if n == 3:
            return 2
        multi_3 = 0
        while n > 4:
            multi_3 += 1
            n -= 3
        return 3**multi_3*n



s = Solution()
print(s.dynamic_programming(8))
print(s.greedy_algorithm(4))