LintCode 801 · Backpack X.java

Backpack with Value array:
note that: "And the number of these merchandises can be considered as infinite."
function:
dp[i] |= dp[i - nums[j] * k]; (when you take that ith item)
or
dp[i] = false; (when you don't take that ith item)

	public class Solution {
	/**
	* @param n: the money you have
	* @return: the minimum money you have to give
	*/
	public int backPackX(int target) {
	// write your code here
	if (target == 0) {
	return 0;
	}
	boolean[] dp = new boolean[target + 1];
	// dp: init
	dp[0] = true;
	// dp: states + functions
	int maximum = Integer.MIN_VALUE;
	int[] nums = new int[]{150, 250, 350};
	for (int i = 1; i <= target; i++) {
	for (int j = 0; j <= 2; j++) {
	int k = 1;
	while (i >= nums[j] * k) {
	dp[i] |= dp[i - nums[j] * k];
	k++;
	}
	}
	if (dp[i]) {
	maximum = i;
	}
	}
	// dp: answer
	return target - maximum;
	}
	}

view raw 801 · Backpack X.java hosted with ❤ by GitHub

LintCode 799 · Backpack VIII.java

Backpack with Value array:
note that: "Each item has different values and quantities."
function:
dp[i][j] |= dp[i - 1][j - A[i - 1] * k]; (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 n: the value from 1 - n
	* @param value: the value of coins
	* @param amount: the number of coins
	* @return: how many different value
	*/
	public int backPackVIII(int m, int[] A, int[] K) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	boolean[][] dp = new boolean[n+1][m+1];
	dp[0][0] = true;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = false;
	}
	// dp: functions
	int counter = 0;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = true;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	for (int k = 1; k <= K[i - 1] && j - A[i - 1] * k >= 0; k++) {
	dp[i][j] |= dp[i - 1][j - A[i - 1] * k];
	}
	if (i == n && dp[i][j]) {
	counter++;
	}
	}
	}
	// for (int i = 0; i <= n; i++) {
	// System.out.println("Arrays.toString(dp[i]) = " + Arrays.toString(dp[i]));
	// }
	// dp: answer
	return counter;
	}
	}

view raw 799 · Backpack VIII.java hosted with ❤ by GitHub

LintCode 798 · Backpack VII.java

Backpack with Value array:
note that: "Given the weight, price and quantity constrains."
function:
dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]); (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 n: the money of you
	* @param prices: the price of rice[i]
	* @param weight: the weight of rice[i]
	* @param amounts: the amount of rice[i]
	* @return: the maximum weight
	*/
	public int backPackVII(int m, int[] A, int[] V, int[] K) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	int k = 1;
	while (j - A[i-1] * k >= 0) {
	dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]);
	k++;
	if (K[i - 1] < k) {
	break;
	}
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 798 · Backpack VII.java hosted with ❤ by GitHub

LintCode 564 · Combination Sum IV.java

Backpack with Value array:
note that: "A number in the array can be used multiple times in the combination."
function:
dp[i] += dp[i - nums[j - 1]]; (when you take that ith item)
or
dp[i] = 0; (when you don't take that ith item)

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

view raw 564 · Combination Sum IV.java hosted with ❤ by GitHub

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

LintCode 562 · Backpack IV.java

Backpack with Value array:
note that: "Each item may be chosen unlimited number of times"
function:
dp[i][j] += dp[i - 1][j - A[i - 1] * k]; (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, no duplicates
	* @param target: An integer
	* @return: An integer
	*/
	public int backPackIV(int[] A, int m) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 1;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 1;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	int k = 1;
	while (j - A[i-1] * k >= 0) {
	dp[i][j] += dp[i - 1][j - A[i - 1] * k];
	k++;
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 562 · Backpack IV.java hosted with ❤ by GitHub

LintCode 440 · Backpack III.java

Backpack with Value array:
note that now you can take k times, or "infinite times"
function:
dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]); (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 A: an integer array
	* @param V: an integer array
	* @param m: An integer
	* @return: an array
	*/
	public int backPackIII(int[] A, int[] V, int m) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	int k = 1;
	while (j - A[i-1] * k >= 0) {
	dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]);
	k++;
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 440 · Backpack III.java hosted with ❤ by GitHub

LintCode 125 · Backpack II.java

Backpack with Value array:
function:
dp[i][j] = Math.max(dp[i - 1][j - A[i - 1]] + V[i - 1], dp[i - 1][j]); (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 m: An integer m denotes the size of a backpack
	* @param A: Given n items with size A[i]
	* @param V: Given n items with value V[i]
	* @return: The maximum value
	*/
	public int backPackII(int m, int[] A, int[] V) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 0;
	for (int j = 1; j <= m; j++) {
	if (j - A[i-1] >= 0) {
	dp[i][j] = Math.max(dp[i - 1][j - A[i - 1]] + V[i - 1], dp[i - 1][j]);
	} else {
	dp[i][j] += dp[i - 1][j];
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 125 · Backpack II.java hosted with ❤ by GitHub

LintCode 92 · Backpack

Classic backpack:
function:
dp[i][j] = dp[i - 1][j];
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i-1]] (if it can fit that ith item, aka: j - A[i-1] >= 0)

	public class Solution {
	/**
	* @param m: An integer m denotes the size of a backpack
	* @param A: Given n items with size A[i]
	* @return: The maximum size
	*/
	public int backPack(int m, int[] A) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	boolean[][] dp = new boolean[n+1][m+1];
	dp[0][0] = true;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = false;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = true;
	for (int j = 1; j <= m; j++) {
	if (j - A[i-1] >= 0 && dp[i - 1][j - A[i-1]]) {
	dp[i][j] = true;
	} else {
	dp[i][j] = dp[i - 1][j];
	}
	if (i == n && dp[i][j]) {
	maximumJ = j;
	}
	}
	}
	// dp: answer
	return maximumJ;
	}
	}

view raw LintCode92 · Backpack.java hosted with ❤ by GitHub

LintCode 76 · Longest Increasing Subsequence

The dp: function is
dp[i] = Math.max(dp[i], dp[l] + 1);

	public class Solution {
	/**
	* @param nums: An integer array
	* @return: The length of LIS (longest increasing subsequence)
	*/
	public int longestIncreasingSubsequence(int[] nums) {
	// write your code here
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int max = 0;
	int n = nums.length;
	int[] dp = new int[n];
	Arrays.fill(dp, 1);
	for (int i = 0; i < n; i++) {
	for (int l = 0; l < i; l++) {
	if (nums[i] > nums[l]) {
	dp[i] = Math.max(dp[i], dp[l] + 1);
	}
	}
	max = Math.max(max, dp[i]);
	}
	System.out.println("Arrays.toString(dp) = " + Arrays.toString(dp));
	return max;
	}
	}

view raw LintCode76 · Longest Increasing Subsequence.java hosted with ❤ by GitHub