this module provides two implementations for the rodcutting problem 1 a naive recursive implementation which has an exponential runtime 2 two dynamic programming implementations which have quadratic runtime the rodcutting problem is the problem of finding the maximum possible revenue obtainable from a rod of length n given a list of prices for each integral piece of the rod the maximum revenue can thus be obtained by cutting the rod and selling the pieces separately or not cutting it at all if the price of it is the maximum obtainable solves the rodcutting problem via naively without using the benefit of dynamic programming the results is the same subproblems are solved several times leading to an exponential runtime runtime o2n arguments n int the length of the rod prices list the prices for each piece of rod pii is the price for a rod of length i returns the maximum revenue obtainable for a rod of length n given the list of prices for each piece examples naivecutrodrecursive4 1 5 8 9 10 naivecutrodrecursive10 1 5 8 9 10 17 17 20 24 30 30 constructs a topdown dynamic programming solution for the rodcutting problem via memoization this function serves as a wrapper for topdowncutrodrecursive runtime on2 arguments n int the length of the rod prices list the prices for each piece of rod pii is the price for a rod of length i note for convenience and because python s lists using 0indexing lengthmaxrev n 1 to accommodate for the revenue obtainable from a rod of length 0 returns the maximum revenue obtainable for a rod of length n given the list of prices for each piece examples topdowncutrod4 1 5 8 9 10 topdowncutrod10 1 5 8 9 10 17 17 20 24 30 30 constructs a topdown dynamic programming solution for the rodcutting problem via memoization runtime on2 arguments n int the length of the rod prices list the prices for each piece of rod pii is the price for a rod of length i maxrev list the computed maximum revenue for a piece of rod maxrevi is the maximum revenue obtainable for a rod of length i returns the maximum revenue obtainable for a rod of length n given the list of prices for each piece constructs a bottomup dynamic programming solution for the rodcutting problem runtime on2 arguments n int the maximum length of the rod prices list the prices for each piece of rod pii is the price for a rod of length i returns the maximum revenue obtainable from cutting a rod of length n given the prices for each piece of rod p examples bottomupcutrod4 1 5 8 9 10 bottomupcutrod10 1 5 8 9 10 17 17 20 24 30 30 lengthmaxrev n 1 to accommodate for the revenue obtainable from a rod of length 0 basic checks on the arguments to the rodcutting algorithms n int the length of the rod prices list the price list for each piece of rod throws valueerror if n is negative or there are fewer items in the price list than the length of the rod the best revenue comes from cutting the rod into 6 pieces each of length 1 resulting in a revenue of 6 6 36 solves the rod cutting problem via naively without using the benefit of dynamic programming the results is the same sub problems are solved several times leading to an exponential runtime runtime o 2 n arguments n int the length of the rod prices list the prices for each piece of rod p i i is the price for a rod of length i returns the maximum revenue obtainable for a rod of length n given the list of prices for each piece examples naive_cut_rod_recursive 4 1 5 8 9 10 naive_cut_rod_recursive 10 1 5 8 9 10 17 17 20 24 30 30 constructs a top down dynamic programming solution for the rod cutting problem via memoization this function serves as a wrapper for _top_down_cut_rod_recursive runtime o n 2 arguments n int the length of the rod prices list the prices for each piece of rod p i i is the price for a rod of length i note for convenience and because python s lists using 0 indexing length max_rev n 1 to accommodate for the revenue obtainable from a rod of length 0 returns the maximum revenue obtainable for a rod of length n given the list of prices for each piece examples top_down_cut_rod 4 1 5 8 9 10 top_down_cut_rod 10 1 5 8 9 10 17 17 20 24 30 30 constructs a top down dynamic programming solution for the rod cutting problem via memoization runtime o n 2 arguments n int the length of the rod prices list the prices for each piece of rod p i i is the price for a rod of length i max_rev list the computed maximum revenue for a piece of rod max_rev i is the maximum revenue obtainable for a rod of length i returns the maximum revenue obtainable for a rod of length n given the list of prices for each piece constructs a bottom up dynamic programming solution for the rod cutting problem runtime o n 2 arguments n int the maximum length of the rod prices list the prices for each piece of rod p i i is the price for a rod of length i returns the maximum revenue obtainable from cutting a rod of length n given the prices for each piece of rod p examples bottom_up_cut_rod 4 1 5 8 9 10 bottom_up_cut_rod 10 1 5 8 9 10 17 17 20 24 30 30 length max_rev n 1 to accommodate for the revenue obtainable from a rod of length 0 basic checks on the arguments to the rod cutting algorithms n int the length of the rod prices list the price list for each piece of rod throws valueerror if n is negative or there are fewer items in the price list than the length of the rod the best revenue comes from cutting the rod into 6 pieces each of length 1 resulting in a revenue of 6 6 36
def naive_cut_rod_recursive(n: int, prices: list):
    

    _enforce_args(n, prices)
    if n == 0:
        return 0
    max_revue = float("-inf")
    for i in range(1, n + 1):
        max_revue = max(
            max_revue, prices[i - 1] + naive_cut_rod_recursive(n - i, prices)
        )

    return max_revue


def top_down_cut_rod(n: int, prices: list):
    
    _enforce_args(n, prices)
    max_rev = [float("-inf") for _ in range(n + 1)]
    return _top_down_cut_rod_recursive(n, prices, max_rev)


def _top_down_cut_rod_recursive(n: int, prices: list, max_rev: list):
    
    if max_rev[n] >= 0:
        return max_rev[n]
    elif n == 0:
        return 0
    else:
        max_revenue = float("-inf")
        for i in range(1, n + 1):
            max_revenue = max(
                max_revenue,
                prices[i - 1] + _top_down_cut_rod_recursive(n - i, prices, max_rev),
            )

        max_rev[n] = max_revenue

    return max_rev[n]


def bottom_up_cut_rod(n: int, prices: list):
    
    _enforce_args(n, prices)

    
    
    max_rev = [float("-inf") for _ in range(n + 1)]
    max_rev[0] = 0

    for i in range(1, n + 1):
        max_revenue_i = max_rev[i]
        for j in range(1, i + 1):
            max_revenue_i = max(max_revenue_i, prices[j - 1] + max_rev[i - j])

        max_rev[i] = max_revenue_i

    return max_rev[n]


def _enforce_args(n: int, prices: list):
    
    if n < 0:
        msg = f"n must be greater than or equal to 0. Got n = {n}"
        raise ValueError(msg)

    if n > len(prices):
        msg = (
            "Each integral piece of rod must have a corresponding price. "
            f"Got n = {n} but length of prices = {len(prices)}"
        )
        raise ValueError(msg)


def main():
    prices = [6, 10, 12, 15, 20, 23]
    n = len(prices)

    
    
    expected_max_revenue = 36

    max_rev_top_down = top_down_cut_rod(n, prices)
    max_rev_bottom_up = bottom_up_cut_rod(n, prices)
    max_rev_naive = naive_cut_rod_recursive(n, prices)

    assert expected_max_revenue == max_rev_top_down
    assert max_rev_top_down == max_rev_bottom_up
    assert max_rev_bottom_up == max_rev_naive


if __name__ == "__main__":
    main()