This is the 15th day of my participation in Gwen Challenge
State compression DP
The key to state-compressed DP is how to express the f(x) function. This kind of questions have several characteristics:
- X usually represents an array that is A subset of the original array A[] : each element in the array A[] may or may not be selected;
- It’s not particularly convenient to write f(x) directly in hashes or arrays;
- The original array A[] is not particularly long.
Based on such a feature, when we design f(x) function, we need to solve the problem according to the following two points:
- The A[I] element may or may not be selected;
- The original array A[] is not particularly long.
Select and unselect can be represented by 0/1. Although x represents an array, the ith bit can be represented by A binary integer y that is as long as (or longer than) the original array: 0 indicates that A[I] is not selected, and 1 indicates that A[I] is selected.
Thus, an array of x can be represented by an integer y, and then the state of f(x) can be represented by the array dp[y]. So let’s do an example. There is a very simple integer representing the information of an array, so this DP is also called state compressed DP.
Example: the maximum fraction sum of N operations
The title
I give you A[], which is an array of positive integers of size 2 by n. You have to perform n operations on this array. For operation I (operation number starting from 1), you need:
Step 1. Select two elements x and y.
Step 2. Obtain scores I * GCD (x, y).
Step 3. Delete x and y from A[].
After returning n times, find the score and the maximum. The function GCD (x, y) is the greatest common divisor of x and y.
Input: A = [3,4,6,8]
Output: 11
Explanation: The optimal operation is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
Note: The maximum length of the array is 14.
Analysis of the
So when we get this problem, let’s first simplify it, turn this problem into an equivalent problem.
Given the delete operation, we can place the deleted element in an array C[] as follows:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
Can also be considered as:
- <3, 6> = 1 * GCD (3, 6)), C = [3, 6]
- <4, 8> = (2 * GCD (4, 8), C = [3, 6, 4, 8]
- The final return is equal to 11
And they could simplify it like this.
You start with an empty array C and an array A[] with elements. You need to do the following:
Select two numbers x,y from A and delete them from A[];
Put these two numbers in C;
Get the score Len (C) / 2 * GCD (x, y).
Figure out how to operate to get the maximum score.
The nice thing about this is that instead of keeping track of the number of steps, we can just look at the size of the current array C and get the current number of steps. So the number of steps is equal to the size of the C array divided by 2.
Next, we will make an analysis based on this slightly modified equivalent problem. Note two pieces of information:
- The maximum
- The array itself is not too big
So let’s analyze the first piece of information and get the maximum, so let’s try DP here. And the second piece of information tells us that if you do a violent search, there are actually only 2N states in the space. It’s not particularly big.
Let’s look at how to make good use of these two important pieces of information.
1. Last step
By the time we get to the last step, there are definitely only two numbers left in the array. Assuming that these two numbers are <x, y>, then in the last step, the payoff is:
Last_step = len(C) + 2/2; Last_income = last_step * GCD (x,y) + last_step * GCD (x,y)Copy the codeHowever, the final two remaining numbers <x, y> can be any two numbers of the original array A[]. So we can express it in pseudocode as follows:
last_income = 0; for (int j = 0; j < N; j++): // x = a[j] for (int k = j + 1; k < N; k++): // array C[] <x,y> Last_step = len(C) + 2/2 = len(A) / 2 last_income = Max ((last_step * GCD (A[j], A[k]), last_step * GCD (A[j], A[k])); last_income);Copy the code2. The problem of child
After studying the last step, it can be found that the maximum return of array C[] and array A[] is to be calculated recursively, so the sub-problem can be expressed as follows:
- F (A) represents the maximum return of array A[];
- F (C) represents the maximum yield of array C[].
We can use F (x) to represent the final problem and sub-problem uniformly:
F (x) represents the maximum return of the array x[]; Where x[] is A subsequence of the original array A[].
3. Recursive relationships
We can rephrase this recursion using pseudocode as follows (explained in the comments) :
Int f(x[]) {// Form array x[] ans = 0; for (int j = 0; j < N; j++): for (int k = j + 1; k < N; k++): C[] = x.remove_index_item(j, k) L = len(x) / 2; / / C [] array formed after join < x > y x array ans = Max ((f (C) + L * GCD (A [j], A [k]), ans); return ans; }Copy the code4. Expression of F (x)
Because array X is definitely A subset of array A, and array A is not particularly large. So we can use binary string to express whether A[I] element exists in the x array:
- 1 indicates that A[I] exists in the x array;
- 0 means that A[I] does not exist in the x array.
In this case, we can apply an array:
int[] dp = new int[1<<(len(A))];
Copy the codeAnd then dp[I] for f(x). Where the binary string of the integer I represents the subsequence x[] of the array A[].
5. Initial conditions and boundaries
First of all, when the array is empty, there is absolutely nothing to gain. So dp[0] = 0. And since we always add elements in pairs, it should be impossible to handle the odd number of bits 1 in the subscript I in dp[I] (indicating that the array x[] has an odd number of elements).
6. Compute the order
When we use the changed topic for processing, we can calculate directly from dp[0].
The complete code
With state compression, we can write code like this (resolved in comments) :
class Solution{
private int bitCount(int x) {
int ret = 0;
while(x ! =0) {
ret += (x & 0x01) = =1 ? 1 : 0;
x >>= 1;
}
return ret;
}
private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
public int maxScore(int[] A) {
final int N = A == null ? 0 : A.length;
final int total_steps = N >> 1;
// There are N numbers
// Each number can represent either presence or absence
// Then there are only two states 0/1
// Therefore, we can use binary representation
// N <= 7
// Therefore, only 14 bits are needed at most
// Then with an int bit, we can express it
// so we apply dp[array_size]
final int array_size = 1 << N;
int[] dp = new int[array_size];
// dp[0] = 0
// indicates that when there are no numbers, the payoff must be 0
// It has already been set, no need to set it again
// Start with the remaining two numbers
// Go ahead
for (int i = 3; i < array_size; i++) {
// use GCC's built-in function to calculate the number of 1's in binary integers
int cnt = bitCount(i);
// Since two numbers need to be removed at a time, when the number of binary ones in I is
// When odd, there is no need to calculate!
if ((cnt & 0x01) = =1) {
continue;
}
// The current number of steps
// that is: what step am I in now
final int cur_step = cnt >>> 1;
// So we need to pick two numbers from I
for (int j = 0; j < N; j++) {
// if I does not have A[j]
if ((i & (1 << j)) == 0)
continue;
for (int k = j + 1; k < N; k++) {
// if there is no A[k] in I
if ((i & (1 << k)) == 0)
continue;
// select A[j], A[k]
final int g = gcd(A[j], A[k]);
/ / score
final int score = cur_step * g;
// get the state after removing I and j
final int mask = (1 << j) | (1 << k);
final int pre_status = i & ~mask;
final int total = dp[pre_status] + score;
// select the maximum value dp[I]dp[i] = Math.max(dp[i], total); }}}return dp[array_size - 1]; }}Copy the codeComplexity analysis: When N numbers are given, a total of 2N states need to be expressed, and each state needs to be traversed N x N times during processing. Therefore, the time complexity is O(2N x N x N), and the space complexity is O(2N). It may seem large, but the problem makes it clear that the length of the array is <= 14 (7 logarithms at most).
summary
The key to this DP problem is the representation of f of x.