require "minitest/autorun"

def cut_rod(p, n)
  return 0 if n == 0

  q = -1
  1.upto(n) do |i|
    q = [q, p[i] + cut_rod(p, n - i)].max
  end
  q
end

def memoized_cut_rod_aux(p, n, r)
  return r[n] if r[n] >= 0
  return 0 if n == 0

  q = -1
  1.upto(n) do |i|
    q = [q, p[i] + memoized_cut_rod_aux(p, n-i, r)].max
  end
  r[n] = q
  q
end

def memoized_cut_rod(p, n)
  r = []
  0.upto(n) do |i|
    r[i] = -1
  end
  memoized_cut_rod_aux(p, n, r)
end

def bottom_up_cut_rod(p, n)
  r = [0]
  1.upto(n) do |j|
    q = -1
    1.upto(j) do |i|
      q = [q, p[i] + r[j-i]].max
    end
    r[j] = q
  end
  r[n]
end

class RodCuttingTest < Minitest::Test
  def setup
    @prices =      [ 0,  1,  5,  8,  9, 10, 17, 17, 20, 24, 30]
    @max_revenue = [ 0,  1,  5,  8, 10, 13, 17, 18, 22, 25, 30]
    @max_cuts =    [ 0,  1,  2,  3,  2,  2,  6,  1,  2,  3, 10]
  end

  def test_recursive_rod_cutting
    0.upto(10) do |n|
      assert_equal @max_revenue[n], cut_rod(@prices, n), "n: #{n}"
    end
  end

  def test_top_down_dynamic_programming_approach
    0.upto(10) do |n|
      assert_equal @max_revenue[n], memoized_cut_rod(@prices, n), "n: #{n}"
    end
  end

  def test_bottom_up_dynamic_programming_approach
    0.upto(10) do |n|
      assert_equal @max_revenue[n], bottom_up_cut_rod(@prices, n), "n: #{n}"
    end
  end
end