Simple dynamic programming for pick nums && two num sums

simple_dp.rb

require 'benchmark'
arr = (1..35).to_a.sort_by{ rand }

def rec_opt(arr, i)
  if i == 0
    arr[0]
  elsif i == 1
    [arr[0], arr[1]].max
  else
    val_a = rec_opt(arr, i-2) + arr[i]
    val_b = rec_opt(arr, i-1)
    [val_a, val_b].max
  end
end
puts Benchmark.realtime {
  puts "rec_opt: #{rec_opt(arr, arr.length-1)}"
}
def dp_opt(arr)
  opt_arr = []
  opt_arr[0] = arr[0]
  opt_arr[1] = [arr[0], arr[1]].max
  (2...arr.length).each do |i|
    val_a = opt_arr[i-2] + arr[i]
    val_b = opt_arr[i-1]
    opt_arr[i] = [val_a, val_b].max
  end
  opt_arr[-1]
end
puts Benchmark.realtime {
  puts "dp_opt: #{dp_opt(arr)}"
}

sum = (1..44).to_a.sort_by{ rand }
ans =  (rand*177).round
def rec_subset(arr, i, s)
  if s == 0
    true
  elsif i == 0
    arr[i] == s
  elsif arr[i] > s
    rec_subset(arr, i-1, s)
  else
    val_a = rec_subset(arr, i-1, s-arr[i])
    val_b = rec_subset(arr, i-1, s)
    val_a || val_b
  end
end
puts Benchmark.realtime {
  puts "rec_subset: #{rec_subset(sum,sum.length-1, ans)}"
}

def dp_subset(arr, s)
  sub_arr = (0...arr.length).map { [0] * (s + 1) }
  sub_arr.each { |row| row[0] = true }
  sub_arr[0] = sub_arr[0].map.with_index { |_, i| i == arr[0] }
  (1...arr.length).each do |i|
    (1...(s + 1)).each do |j|
      if arr[i] > j
        sub_arr[i][j] = sub_arr[i - 1][j]
      else
        val_a = sub_arr[i - 1][j - arr[i]]
        val_b = sub_arr[i - 1][j]
        sub_arr[i][j] = val_a || val_b
      end
    end
  end
  sub_arr[-1][-1]
end
puts Benchmark.realtime {
  puts "dp_subset: #{rec_subset(sum,sum.length-1, ans)}"
}