LintCode 563 · Backpack V.java

Backpack with Value array:
note that: "Each item may only be used once"
function:
dp[i][j] += dp[i - 1][j - nums[i - 1]]; (when you take that ith item)
or
dp[i][j] += dp[i - 1][j]; (when you don't take that ith item)

	public class Solution {
	/**
	* @param nums: an integer array and all positive numbers
	* @param target: An integer
	* @return: An integer
	*/
	public int backPackV(int[] nums, int target) {
	// write your code here
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int n = nums.length;
	int[][] dp = new int[n + 1][target + 1];
	// dp: init
	dp[0][0] = 1;
	for (int j = 1; j <= target; j++) {
	dp[0][j] = 0;
	}
	// dp: states + functions
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 1;
	for (int j = 1; j <= target; j++) {
	dp[i][j] = dp[i - 1][j];
	if (nums[i-1] <= j) {
	dp[i][j] += dp[i - 1][j - nums[i - 1]];
	}
	}
	}
	// dp: answer
	return dp[n][target];
	}
	}

view raw 563 · Backpack V.java hosted with ❤ by GitHub