Python O(n) DP solution


  • 1
    K
    class Solution(object):
        def integerBreak(self, n):
            """
            :type n: int
            :rtype: int
            """
            dp = [0,0,1,2,4,6,9]
            for i in range(7,n+1): dp += max(3*dp[i-3], 2*dp[i-2]),
            return dp[n]

  • 0
    F

    Could you please elaborate?
    Thanks.


  • 0
    P

    a more generalized one (but longer):

    dp = [0,0,1]
    for i in range(3,n+1):
        dp += [max(3*max(dp[i-3],i-3), 2*max(dp[i-2],i-2), 1*max(dp[i-1],i-1))]
    return dp[n]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.