Challenge

Given a rod of length N. You are also given an array that represents the revenue of each cut size. You want to maximize revenue. E.g : [2,3,7,8], piece of length 1 gets you 2$.

Solution

Top down with Memoization:

class Solution:

    def helper(self, n, cost):
        if n < 0:
            return 0
        if n == 0:
            return cost
        if n in self.memo:
            return self.memo[n]
        res = 0
        for i in range(1, len(self.cost)+1):
            res = max(res, self.helper(n-i, cost + self.cost[i]))
        self.memo[n] = res
        return self.memo[n]

    def rodCutting(self, n, cuts):
        self.res = 0
        self.memo = {}
        cost  = {}
        for i, e in enumerate(cuts):
            cost[i+1] = e
        self.cost = cost
        return self.helper(n, 0)