Number of Ways to Represent N Cents

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

Example:

n = 11

11 = 1 + 1 + 1... + 1
   = 1 + 1 + 1 + 1 + 1 + 1 + 5
   = 1 + 5 + 5
   = 1 + 10

return 4

Solution:

We first find the number of ways by using 1 cent, then we add the number of ways by using 5 cents onto that. We repeat this process for each kind of coins.

Code:

public class Solution {

    public int waysNCents(int n) {

        int[] coins = new int[] {1, 5, 10, 25};
        int[] f = new int[n + 1];

        f[0] = 1;

        for (int i = 0; i < coins.length; i++) {
            for (int j = 1; j <= n; j++) {
                if (j >= coins[i]) {
                    f[j] = f[j] + f[j - coins[i]];
                }
            }
        }
        return f[n];
    }
}