[POH3]天才火消しエンジニア霧島 京子 ref: http://qiita.com/pocari/items/e2a87ff905a05f61c361

file1.txt

INF = 500 * 5000000 + 1
m, n = 2.times.map{gets.chomp.to_i}

dp = [0] + Array.new(m, INF)
n.times do
  num, cost = gets.chomp.split(/ /).map(&:to_i)
  m.downto(1) do |j|
    prev = j - num
    prev = 0 if prev < 0

    use = dp[prev] + cost
    dp[j] = use if use < dp[j]
  end
end

puts dp[m]

poh3.rb

m = gets.chomp.to_i
n = gets.chomp.to_i

dp = Array.new(m + 1,Float::INFINITY)
dp[0] = 0

n.times do
  num, cost = gets.chomp.split(/ /).map(&:to_i)

  ndp = Array.new(m + 1, Float::INFINITY)
  ndp[0] = 0

  (1 .. m).each do |j|
    prev = j - num
    prev = 0 if prev < 0

    non_use = dp[j]
    use = dp[prev] + cost
    if non_use < use
      ndp[j] = non_use
    else
      ndp[j] = use
    end
  end
  dp = ndp
end

puts dp[m]