dynamic_programming.rod_cutting
===============================

.. py:module:: dynamic_programming.rod_cutting

.. autoapi-nested-parse::

   This module provides two implementations for the rod-cutting problem:
     1. A naive recursive implementation which has an exponential runtime
     2. Two dynamic programming implementations which have quadratic runtime

   The rod-cutting 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.



Functions
---------

.. autoapisummary::

   dynamic_programming.rod_cutting._enforce_args
   dynamic_programming.rod_cutting._top_down_cut_rod_recursive
   dynamic_programming.rod_cutting.bottom_up_cut_rod
   dynamic_programming.rod_cutting.main
   dynamic_programming.rod_cutting.naive_cut_rod_recursive
   dynamic_programming.rod_cutting.top_down_cut_rod


Module Contents
---------------

.. py:function:: _enforce_args(n: int, prices: list)

   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


.. py:function:: _top_down_cut_rod_recursive(n: int, prices: list, max_rev: list)

   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.


.. py:function:: bottom_up_cut_rod(n: int, prices: list)

   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


.. py:function:: main()

.. py:function:: naive_cut_rod_recursive(n: int, prices: list)

   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


.. py:function:: top_down_cut_rod(n: int, prices: list)

   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