Dynamic programming - Coin change decision

My solution below is a greedy approach calculating all the solutions and cacheing the latest optimal one. If current executing solution is already larger than cached solution abort the path. Note, for best performance denomination should be in decreasing order.

import java.util.ArrayList;
import java.util.List;

public class CoinDenomination {

    int denomination[] = new int[]{50,33,21,2,1};
    int minCoins=Integer.MAX_VALUE;
    String path;

    class Node{
        public int coinValue;
        public int amtRemaining;
        public int solutionLength;
        public String path="";
        public List<Node> next;

        public String toString() { return "C: "+coinValue+" A: "+amtRemaining+" S:"+solutionLength;}
    }

    public List<Node> build(Node node)
    {
        if(node.amtRemaining==0)
        {
            if (minCoins>node.solutionLength) {
                minCoins=node.solutionLength;
                path=node.path;
            }
            return null;
        }

        if (node.solutionLength==minCoins) return null;
        List<Node> nodes = new ArrayList<Node>();
        for(int deno:denomination)
        {
           if(node.amtRemaining>=deno)
           {
               Node nextNode = new Node();
               nextNode.amtRemaining=node.amtRemaining-deno;
               nextNode.coinValue=deno;
               nextNode.solutionLength=node.solutionLength+1;
               nextNode.path=node.path+"->"+deno;
               System.out.println(node);
               nextNode.next = build(nextNode);
               nodes.add(node);

           }
        }

        return nodes;
    }

    public void start(int value)
    {
        Node root = new Node();
        root.amtRemaining=value;
        root.solutionLength=0;
        root.path="start";
        root.next=build(root);
        System.out.println("Smallest solution of coins count: "+minCoins+" \nCoins: "+path);
    }

    public static void main(String args[])
    {
        CoinDenomination coin = new CoinDenomination();
        coin.start(35);
    }
}

Your code is a good start. The usual way to convert a recursive solution to a dynamic-programming one is to do it "bottom-up" instead of "top-down". That is, if your recursive solution calculates something for a particular X using values for smaller x, then instead calculate the same thing starting at smaller x, and put it in a table.

In your case, change your MakeChange recursive function into a canMakeChange table.

canMakeChange[0] = True
for X = 1 to (your max value):
   canMakeChange[X] = False
   for i=1 to n:
     if X>=x[i] and canMakeChange[X-x[i]]==True: 
       canMakeChange[X]=True