Solution to https://www.interviewbit.com/problems/rod-cutting/

sol.py

import sys
class Solution:

    def __init__(self):
        self.valid_cuts = None
        self.memo = None

    # left and right indices of a sorted list of valid cuts
    # [4,5,7,8]

    # returns (the path, cost)
    def _rodCut(self, left_idx, right_idx): # returns the minimum cost for that particular subtree
        if self.memo[left_idx][right_idx] is not None:
            return self.memo[left_idx][right_idx]

        if right_idx - left_idx == 1: # base case
            return ([], 0) # NOT self.valid_cuts[right_idx] - self.valid_cuts[left_idx] because we DID NOT END UP CUTTING

        _min = sys.maxsize
        _path = None
        _selected_i = None
        for i in range(left_idx + 1, right_idx):
            # perform cuts here
            (_lpath, _lcost) = self._rodCut(left_idx, i)
            (_rpath, _rcost) = self._rodCut(i, right_idx)

            if _lcost + _rcost < _min:
                _selected_i = i
                _min = _lcost + _rcost

                _lstepcost = -1 if not len(_lpath) else _lpath[0]
                _rstepcost = -1 if not len(_rpath) else _rpath[0]

                _path = [ self.valid_cuts[_selected_i] ]
                _path.extend(_lpath + _rpath if _lstepcost < _rstepcost else _rpath + _lpath)

        # _path = [ self.valid_cuts[_selected_i] ] + _path
        _min += self.valid_cuts[right_idx] - self.valid_cuts[left_idx]

        self.memo[left_idx][right_idx] = (_path, _min)
        return self.memo[left_idx][right_idx]

    # @param A : integer
    # @param B : list of integers
    # @return a list of integers
    def rodCut(self, A, B):
        self.valid_cuts = sorted(B)
        self.valid_cuts.append(A)
        self.valid_cuts = [0] + self.valid_cuts

        self.memo = [ [None]*len(self.valid_cuts) for i in range(len(self.valid_cuts)) ]

        (_path, _cost) = self._rodCut(0, len(self.valid_cuts) - 1)
        return _path