# Path: clrs/_src/algorithms/dynamic_programming.py
# def matrix_chain_order(p: _Array) -> _Out:
# def lcs_length(x: _Array, y: _Array) -> _Out:
# def optimal_bst(p: _Array, q: _Array) -> _Out:


from absl.testing import absltest
from clrs._src.algorithms import dynamic_programming
import numpy as np
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
# ==============================================================================

"""Unit tests for `dynamic_programming.py`."""




class DynamicProgrammingTest(absltest.TestCase):

  def test_matrix_chain_order_1(self):

    expected = np.array([
        [0, 1, 1, 3, 3, 3],
        [0, 0, 2, 3, 3, 3],
        [0, 0, 0, 3, 3, 3],
        [0, 0, 0, 0, 4, 5],
        [0, 0, 0, 0, 0, 5],
        [0, 0, 0, 0, 0, 0],
    ])
    for shift in [0, 1, 2]:
      for scale in [1, 3, 17]:
        ps = shift + scale * np.array([30, 35, 15, 5, 10, 20, 25])

# Path: clrs/_src/algorithms/dynamic_programming.py
# def matrix_chain_order(p: _Array) -> _Out:
# def lcs_length(x: _Array, y: _Array) -> _Out:
# def optimal_bst(p: _Array, q: _Array) -> _Out:


# Path: clrs/_src/algorithms/dynamic_programming_test.py
from absl.testing import absltest
from clrs._src.algorithms import dynamic_programming
import numpy as np

#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
# ==============================================================================

"""Unit tests for `dynamic_programming.py`."""




class DynamicProgrammingTest(absltest.TestCase):

  def test_matrix_chain_order_1(self):

    expected = np.array([
        [0, 1, 1, 3, 3, 3],
        [0, 0, 2, 3, 3, 3],
        [0, 0, 0, 3, 3, 3],
        [0, 0, 0, 0, 4, 5],
        [0, 0, 0, 0, 0, 5],
        [0, 0, 0, 0, 0, 0],
    ])
    for shift in [0, 1, 2]:
      for scale in [1, 3, 17]:
        ps = shift + scale * np.array([30, 35, 15, 5, 10, 20, 25])

        order, _ = dynamic_programming.matrix_chain_order(ps)