LeetCode dynamic programming topic Javascript language detailed analysis 2.0
1. 0-1 Backpack Basics
Two-dimensional array
function testWeightBagProblem(weight, value, size) {
//size is the capacity of the backpack
const len = weight. length,
dp = new Array(len).fill(0).map(() => new Array(size + 1).fill(0));
//If the item starts from 0, the backpack starts from 0, and the length to size must be size+1, because the value of size is the weight of the backpack, and it needs to reach size
console. log(dp);
for (let j = weight[0]; j <= size; j++) {
dp[0][j] = value[0];
}
//Loop through items first
for (let i = 1; i < len; i++) {
// You can traverse from back to front like scrolling an array, so you don't need to judge if
// for (let j = size; j >= weight[i]; j--) {
// dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
// }
// The knapsack traverses from front to back, j starts from 1, because the knapsack capacity j is at least 1
for (let j = 1; j <= size; j++) {
if (weight[i] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
return dp[len - 1][size];
}
Scroll array
function testWeightBagProblem(weight, value, size) {
let dp = new Array(size + 1).fill(0);
// j is the capacity of the backpack, and the value of the capacity is directly j,
//It is not necessary to initialize first, because the value of the next backpack is based on the previous one, but if it is not initialized, i will start from 0
for (let i = 0; i < weight. length; i++) {
for (let j = size; j >= weight[i]; j--) {
// No if statement, because j is already greater than or equal to weight[i]
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[size];
}
2. Partition Equal Subset Sum
Partition Equal Subset Sum
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
thinking
- The volume of the knapsack is sum / 2
- The weight of the product (the element in the collection) to be put in the backpack is the value of the element, and the value is also the value of the element
- If the knapsack is exactly full, it means that a subset with a sum of sum / 2 has been found.
- Each element in the backpack cannot be placed repeatedly.
After the above analysis, we can apply the 01 backpack to solve this problem
/*
Determine whether the array can be divided according to the length n of the array. If n<2, it is impossible to split the array into two subsets whose elements are equal, so return false directly.
Computes the element sum of the entire array and the largest element maxNum. If sum is odd, it is not possible to split the array into two subsets whose elements are equal,
For an even number, set target= 2/sum, if maxNum is greater than target, return false directly
*/
var canPartition = function (nums) {
if (nums. length < 2) return false;
let sum = 0,
max = nums[0];
for (let v of nums) {
sum += v;
max = v > max ? v : max;
}
if (sum % 2 === 1 ||max>sum/2) return false; // sum is inseparable for odd numbers
let target = sum / 2; //To be divided into sum/2, that is, the size of the backpack is sum/2
let dp = new Array(target + 1).fill(0);
for (let i = 0; i < nums. length; i++) {
for (let j = target; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
if (dp[j] === target) return true; // find a backpack that meets the conditions and return
}
}
return dp[target] === sum / 2;
};
3. Last Stone Weight II
Last Stone Weight II
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0
thinking
This question is actually trying to divide the stones into two piles of the same weight, and the remaining stones after the collision are the stones with the smallest weight, so it is converted into a 0-1 knapsack problem
/* Idea: Minimize the absolute value of the weight difference between the two piles of stones
When calculating target, target = sum / 2 because it is rounded down, so sum - dp[target] must be greater than or equal to dp[target].
Then the minimum stone weight left after the collision is (sum - dp[target]) - dp[target]
*/
var lastStoneWeightII = function (stones) {
let sum = stones. reduce((s, n) => s + n);
let dpLen = Math. floor(sum / 2);
let dp = new Array(dpLen + 1).fill(0);
for (let i = 0; i < stones. length; ++i) {
for (let j = dpLen; j >= stones[i]; --j) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[dpLen] - dp[dpLen];
};
4. Target Sum
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1". Return the number of different expressions that you can build, which evaluates to target.
/*
The sum of the elements of the array is sum, the sum of the elements added with - sign is neg, then the sum of the elements added with + is sum−neg, and the result of the obtained expression is
(sum−neg)−neg=sum−2⋅neg=target, ie neg= (sum−target)/2
If j ≥ num, then if num is not selected, the number of plans is dp[i−1][j], if the number of plans is dp[i−1][j−num], then there is dp[i][j ]=dp[i−1][j]+dp[i−1][j−num]
If the rolling array is used, the recursive formula for filling the knapsack is: dp[j] +=dp[j-nums[i]]
It can be seen from the recursive formula that dp[0] must be initialized to 1 during initialization, because dp[0] is the origin of all recursive results in the formula. If dp[0] is 0, the recursive results will be all is 0.
dp[0] = 1, which is also well explained in theory. There is one way to fill a backpack with a capacity of 0, which is to load 0 items.
*/
var findTargetSumWays = function (nums, target) {
/*The sum of the elements of the array is sum, the sum of the elements added with - sign is neg, then the sum of the other elements added with + is sum−neg, and the result of the obtained expression is
(sum−neg)−neg=sum−2⋅neg=target, ie neg= (sum−target)/2
*/
let sum = 0;
for (let v of nums) {
sum += v;
}
let diff = sum - target;
if (diff < 0 || diff % 2 !== 0) return 0;
let dp = new Array(diff / 2 + 1).fill(0);
dp[0] = 1; //Initialize dp[0] because the following cycle will be used, which is equivalent to the capacity of 0 to hold 0 things, there is only one way
for (let i = 0; i < nums. length; i++) {
for (let j = diff / 2; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[diff / 2];
};
In the case that there are several ways to fill the backpack, the recursive formula is generally:
dp[j] += dp[j - nums[i]];
5. Ones and Zeroes
You are given an array of binary strings strs and two integers m and n. Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset. A set x is a subset of a set y if all elements of x are also elements of y.
The elements in the strs array in this question are items, and each item is one, while m and n are equivalent to a backpack, a two-dimensional backpack.
var findMaxForm = function (strs, m, n) {
let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
let zeros, ones;
//Scroll the array, traverse the items first
for (let value of strs) {
//Initialize the value of 0 and 1 to 0 for each cycle to count the number of 0 and 1 for each item, that is, the weight of each item
(zeros = 0), (ones = 0);
for (let v of value) {
if (v === '0') zeros++;
else ones++;
}
//Knapsack traversal, the capacity of the backpack is m and n respectively, both must meet the conditions
for (let i = m; i >= zeros; i--) {
for (let j = n; j >= ones; j--) {
// Find the length, so add one
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
};
