# 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
  def test_matrix_chain_order_2(self):

    expected = np.array([
        [0, 1, 2, 2, 4, 2],
        [0, 0, 2, 2, 2, 2],
        [0, 0, 0, 3, 4, 4],
        [0, 0, 0, 0, 4, 4],
        [0, 0, 0, 0, 0, 5],
        [0, 0, 0, 0, 0, 0],
    ])

    for shift in [0, 1]:
      for scale in [1, 3, 17]:
        ps = shift + scale * np.array([5, 10, 3, 12, 5, 50, 6])
        order, _ = dynamic_programming.matrix_chain_order(ps)
        np.testing.assert_array_equal(expected, order)

  def test_lcs_length(self):
    xs = np.array([0, 1, 2, 1, 3, 0, 1])
    ys = np.array([1, 3, 2, 0, 1, 0])

    expected = np.array([
        [1, 1, 1, 0, 2, 0],
        [0, 2, 2, 1, 0, 2],
        [1, 1, 0, 2, 1, 1],
        [0, 1, 1, 1, 0, 2],
        [1, 0, 1, 1, 1, 1],
        [1, 1, 1, 0, 1, 0],
        [0, 1, 1, 1, 0, 1],
    ])

# 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

  def test_matrix_chain_order_2(self):

    expected = np.array([
        [0, 1, 2, 2, 4, 2],
        [0, 0, 2, 2, 2, 2],
        [0, 0, 0, 3, 4, 4],
        [0, 0, 0, 0, 4, 4],
        [0, 0, 0, 0, 0, 5],
        [0, 0, 0, 0, 0, 0],
    ])

    for shift in [0, 1]:
      for scale in [1, 3, 17]:
        ps = shift + scale * np.array([5, 10, 3, 12, 5, 50, 6])
        order, _ = dynamic_programming.matrix_chain_order(ps)
        np.testing.assert_array_equal(expected, order)

  def test_lcs_length(self):
    xs = np.array([0, 1, 2, 1, 3, 0, 1])
    ys = np.array([1, 3, 2, 0, 1, 0])

    expected = np.array([
        [1, 1, 1, 0, 2, 0],
        [0, 2, 2, 1, 0, 2],
        [1, 1, 0, 2, 1, 1],
        [0, 1, 1, 1, 0, 2],
        [1, 0, 1, 1, 1, 1],
        [1, 1, 1, 0, 1, 0],
        [0, 1, 1, 1, 0, 1],
    ])

    out, _ = dynamic_programming.lcs_length(xs, ys)