- #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)
来源: http://www.bubuko.com/infodetail-2990343.html