Solving the rod-cutting problem using dynamic programming I've written what I believe is a valid dynamic programming solution to a variation of the rod cutting problem. In this problem, the goal is to make as few cuts as possible on a rod of length n.

I have two questions:


Is this a valid dynamic programming solution?
How can it be improved?


(This is not a school assignment. I simply want to understand dynamic programming better)

public class RodCutting {

    RodCutting(int[] cuts, int length) {
        List&lt;Integer&gt; cutLengths = new ArrayList&lt;Integer&gt;();
        for (int i = 0; i &lt; cuts.length; i++) {
            cutLengths.add(cuts[i]);
        }
        Collections.sort(cutLengths);
        List&lt;List&lt;Integer&gt;&gt; optimalCuts = new ArrayList&lt;List&lt;Integer&gt;&gt;();

        // initialize list
        for (int i = 0; i &lt;= length; i++) {
            optimalCuts.add(new ArrayList&lt;Integer&gt;());
        }

        for (int i = 1; i &lt;= length; i++) {
            // assume 1 is always a valid cut length
            if (cutLengths.contains(i)) {
                for (int j = 0; j &lt; cutLengths.size(); j++) {
                    if (i == cutLengths.get(j)) {
                        optimalCuts.get(i).add(cutLengths.get(j));
                        // nothing larger than the current cut
                    }
                }
            } else {
                for (int j = 0; j &lt; cutLengths.size(); j++) {
                    if (i &gt; cutLengths.get(j)) {
                        List&lt;Integer&gt; newCuts = union(
                                optimalCuts.get(i - cutLengths.get(j)),
                                cutLengths.get(j));
                        if (optimalCuts.get(i).size() == 0
                                || newCuts.size() &lt; optimalCuts.get(i).size()) {
                            optimalCuts.remove(i);
                            optimalCuts.add(i, newCuts);
                        }
                    }
                }
            }
        }

        for (int i = 0; i &lt; optimalCuts.size(); i++) {
            System.out.println(i + ": " + optimalCuts.get(i));
        }

    }

    List&lt;Integer&gt; union(List&lt;Integer&gt; listOfCuts, int additionalCut) {
        List&lt;Integer&gt; returnList = new ArrayList&lt;Integer&gt;(listOfCuts);
        returnList.add(additionalCut);
        return returnList;
    }

    public static void main(String[] args) {
        int[] cuts = { 1, 3, 4, 7 };
        int rodLength = 100;
        RodCutting cut = new RodCutting(cuts, rodLength);
    }
}
I'm not familiar with the problem of rod-cutting, so I cannot reflect on the correctness of the algorithtm.
However, I can give you suggestions for some slight improvements:


union method does not depend on any instance variables --> consider making it static
consider splitting the algorithm into two parts: the constructor could have just some code to store the parameters, and then you could have a separate method to perform the actual calculations (this would make the code more readable)


So, I suggest something like this (not tested):

public class RodCutting {
    private int [] cutLengths;
    private int length;

    RodCutting(int[] cuts, int length) {
        cutLengths = new ArrayList&lt;Integer&gt;();
        for (int i = 0; i &lt; cuts.length; i++) {
            cutLengths.add(cuts[i]);
        }
        Collections.sort(cutLengths);

        this.length = length;
   }

   public void calc() {
        List&lt;List&lt;Integer&gt;&gt; optimalCuts = new ArrayList&lt;List&lt;Integer&gt;&gt;();

        // initialize list
        for (int i = 0; i &lt;= length; i++) {
            optimalCuts.add(new ArrayList&lt;Integer&gt;());
        }

        for (int i = 1; i &lt;= length; i++) {
            // assume 1 is always a valid cut length
            if (cutLengths.contains(i)) {
                for (int j = 0; j &lt; cutLengths.size(); j++) {
                    if (i == cutLengths.get(j)) {
                        optimalCuts.get(i).add(cutLengths.get(j));
                        // nothing larger than the current cut
                    }
                }
            } else {
                for (int j = 0; j &lt; cutLengths.size(); j++) {
                    if (i &gt; cutLengths.get(j)) {
                        List&lt;Integer&gt; newCuts = union(
                                optimalCuts.get(i - cutLengths.get(j)),
                                cutLengths.get(j));
                        if (optimalCuts.get(i).size() == 0
                                || newCuts.size() &lt; optimalCuts.get(i).size()) {
                            optimalCuts.remove(i);
                            optimalCuts.add(i, newCuts);
                        }
                    }
                }
            }
        }

        for (int i = 0; i &lt; optimalCuts.size(); i++) {
            System.out.println(i + ": " + optimalCuts.get(i));
        }

    }

// ... rest of the code