动态规划_leetcode343

#coding=utf-8

# 递归
class Solution1(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """

        self.memo = [-1 for i in range(n+1)]

    # 将n进行分割（至少分割两部分）,可以获得的最大乘积
    def breakInterger(self,n):

        if n == 1:
            return 1

        res = -1

        # i + (n-i)
        for i in range(1,n):
           res = max(res, i* (n-i),self.breakInterger(i))
        return res

# 记忆化递归
class Solution2(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        pass

    # 将n进行分割（至少分割两部分）,可以获得的最大乘积
    def breakInterger(self,n):

        if n == 1:
            return 1

        if self.memo[n] != -1:
            return self.memo[n]



        res = -1

        # i + (n-i)
        for i in range(1,n):
           res = max( res, i* (n-i),self.breakInterger(i))


        self.memo[n] = res

        return self.res



# 动态规划: 先解决最基本的问题，由底向上解决原问题
class Solution3(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.breakInterger(n)

    # 将n进行分割（至少分割两部分）,可以获得的最大乘积
    def breakInterger(self,n):

        # 将n进行分割（至少分割两部分）,可以获得的最大乘积
        memo = [-1 for i in range(n+1)]

        memo[1] = 1

        #memo[n]
        # for i in range(1,n):
        #     memo[n] = max(memo[n],i * (n-i), i * memo[n-i])

        # #memo[2]
        # for i in range(1,2):
        #     memo[2] = max(memo[2],i * (2-i),i*memo[2-i])
        #
        #
        # #memo[3]
        # for i in range(1,3):
        #     memo[3] = max(memo[3],i * (3-i), i *memo[3-i])
        #
        # #memo[4]
        # for i in range(1, 4):
        #     memo[4] = max(memo[4], i * (4 - i), i * memo[4 - i])

        for i in range(1,n+1):
            for j in range(1,i):
                memo[i]  = max(memo[i], j * (i-j) ,j * memo[i-j])

        print memo[n]
        return memo[n]


s = Solution3()

s.integerBreak(10)