Algorithms homework assignment #2 solution.

Main.java

import java.util.*;
import static java.lang.Math.min;

public class Main {

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int distance = in.nextInt(), n = in.nextInt();
    int[] costs = new int[distance + 1];
    Arrays.fill(costs, Integer.MAX_VALUE / 2);
    for (int i = 0; i < n; i++) {
      int len = in.nextInt(), cost = in.nextInt();
      if (len <= distance) {
        costs[len] = min(costs[len], cost);
      }
    }
    for (int i = 2; i <= distance; i++) {
      for (int j = 1; j < i; j++) {
        costs[i] = min(costs[i], costs[j] + costs[i - j]);
      }
    }
    System.out.println(costs[distance]);
  }
}