Wednesday, June 30, 2021

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)

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)

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)

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)

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)

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)

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)

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)

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)

LintCode 76 · Longest Increasing Subsequence

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