def bottom_up_cut_rod(n: int, prices: list):
    '\n    Constructs a bottom-up dynamic programming solution for the rod-cutting problem\n\n    Runtime: O(n^2)\n\n    Arguments\n    ----------\n    n: int, the maximum length of the rod.\n    prices: list, the prices for each piece of rod. ``p[i-i]`` is the\n    price for a rod of length ``i``\n\n    Returns\n    -------\n    The maximum revenue obtainable from cutting a rod of length n given\n    the prices for each piece of rod p.\n\n    Examples\n    -------\n    >>> bottom_up_cut_rod(4, [1, 5, 8, 9])\n    10\n    >>> bottom_up_cut_rod(10, [1, 5, 8, 9, 10, 17, 17, 20, 24, 30])\n    30\n    '
    _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]
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
def bottom_up_cut_rod(n: int, prices: list):
    '\n    Constructs a bottom-up dynamic programming solution for the rod-cutting problem\n\n    Runtime: O(n^2)\n\n    Arguments\n    ----------\n    n: int, the maximum length of the rod.\n    prices: list, the prices for each piece of rod. ``p[i-i]`` is the\n    price for a rod of length ``i``\n\n    Returns\n    -------\n    The maximum revenue obtainable from cutting a rod of length n given\n    the prices for each piece of rod p.\n\n    Examples\n    -------\n    >>> bottom_up_cut_rod(4, [1, 5, 8, 9])\n    10\n    >>> bottom_up_cut_rod(10, [1, 5, 8, 9, 10, 17, 17, 20, 24, 30])\n    30\n    '
    _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]