Guide to Dynamic Programming - I will show the coding result.

Problem: given n, find the number of different ways to write n as the sum of 1, 3, 4

I conclude the method as 4 step solver.

Step 1. Define:
D[n] = number of ways to reach the sum n.

2. Recurrence:
D[n] = D[n - 1] + D[n - 3] + D[n - 4]

3. Base Case
D[0] = 1, D[1] = 1, D[2] = 1, D[3] = 2;
D[negative] = 0,

4. Result Case
D[n]

Time Complexity: O(n * m) - two for loops with n, m length; n is the sum; m is the length of that numbers array.
Space: O(n) - the whole D array

ok, now let's get hands dirty.

	private static void testDynamic1() {
	logger.info("{}", backPackVariation(new int[]{1, 3, 4}, 10));
	}
	static int backPackVariation(int[] numbers, int n) {
	// filter abnormal inputs
	if (numbers == null || numbers.length == 0) {
	return 1;
	}
	// populate the subproblem result array
	int len = numbers.length;
	int[] ret = new int[n + 1];
	ret[0] = 1;
	for (int i = 1; i <= n; i++) {
	for (int j = 0; j < len; j++) {
	if (i - numbers[j] >= 0) {
	ret[i] += ret[i - numbers[j]];
	}
	}
	}
	// print to verify before commiting
	System.out.println(Arrays.toString(ret));
	// return result
	return ret[n];
	}

view raw backPackVariation.java hosted with ❤ by GitHub

Result: [1, 1, 1, 2, 4, 6]
16:09:04:591 [main] INFO com.StandfordDP.Dynamic1 - 6


Reference: http://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf