Line breaks | Line wrapping - Dynamic Programming calculate minimal penalty/badness factor

LineWrap.java

/**
 * @author Loris Reiff	<loris.reiff [a] mailbox.org>
 * 						<loris.reiff [a] hotmail.com>
 * ETH HW - D&A
 * Minimal Line breaks
 */


class LineWrap {
	public static int penalty(int length, int width) {
		if(length > width)
			return Integer.MAX_VALUE;
		return (width-length)*(width-length);
	}
	
	/**
	 * Calculates the minimal penalty/badness factor for line breaks
	 *
	 * @param words The words of a paragraph
	 * @param maxWidth Maximal Width of the lines
	 * @return the minimal badness factor/penalty
	 */
	public static int minimalPenalty(String[] words, int maxWidth) {
		// DP table: minimal penalty with words i to n
		int[] lineMin = new int[words.length];

		for(int i = 0; i < lineMin.length; i++) {
			lineMin[i] = Integer.MAX_VALUE;
		}

		for(int i = words.length-1; i >= 0; i--) {
			int currentWidth = words[i].length();
			int k = 0;		// consider words i to i+k for current line
			while(currentWidth <= maxWidth) {
				// words fit in last line
				if(i+k+1 >= words.length) {
					lineMin[i] = 0;
					break;
				}
				int p = penalty(currentWidth, maxWidth) + lineMin[i + 1 + k];
				if(p < lineMin[i]) {
					lineMin[i] = p;
				}
				// add a word to the line
				k++;
				currentWidth += words[i+k].length() + 1;
			}
		}
		return lineMin[0];
	}

	public static void main(String[] args) {
		String[] words = new String[]{"Hello", "I", "am", "Superman.",
						"How", "nice", "random", "stuff", "here", "we", "go"};
		System.out.println(minimalPenalty(words, 10));
	}
}