Dynamic Programming : Number of ways to.….

When it comes to solving questions asking for the number of ways to be king of the world, or something simpler — the number of ways to generate a specific coin change — use Dynamic programming.

Question from Elements of Programming interviews :

In a game, a play may lead up to 2 points, or 3 points, or 7 points. Many different combinations of 2 points, 3 points, or 7 points can lead to a final score.

Amount = 12, Point options : {2, 3, 7}

Let’s move to stage 1 :

Coming up with a recursive solution :

public static int
numCombinationsForFinalScore(int finalScore,
                             List<Integer> individualPlayScores) {
  return recurse(finalScore, 0, individualPlayScores, 0);
}

private static int recurse(int finalScore, int sum, List<Integer> individualPlayScores, int index) {
  if (index >= individualPlayScores.size())
    return 0;
  if (sum == finalScore)
    return 1;
  int val = 0;
  if (sum + individualPlayScores.get(index) <= finalScore)
    val = recurse(finalScore, sum + individualPlayScores.get(index), individualPlayScores, index);
  val += recurse(finalScore, sum, individualPlayScores, index+1);
  return val;
}

Next, let us look at bottom-up solution :

public static int numCombinationsForFinalScore(int finalScore,
                             List<Integer> individualPlayScores) {
  int[][] dp = new int[individualPlayScores.size() +…