This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging
Topic describes
This is 526 from LeetCode. Elegant arrangement, medium difficulty.
Tag: “bit operation”, “pressure DP”, “dynamic programming”
Suppose there are NNN integers from 111 to NNN, and if an array is successfully constructed from these NNN numbers such that bit III of the array (1<= I <=N1 <= I <=N1 <= I <= I <= I <=N) satisfies one of two conditions, the array is said to be a beautiful arrangement.
Condition:
- Digit iii is divisible by iii
- Iii is divisible by the number in position III
Now, given an integer NNN, how many graceful permutations can be constructed?
Example 1:
Input: 2 Output: 2 Explanation: The first graceful arrangement is [1, 2]: the number in the first position (I =1) is 1, 1 is divisible by I (I =1). The number in the second position (I =2) is 2, 2 is divisible by I (I =2). The number in the first position (I =1) is 2, 2 is divisible by I (I =1), and the number in the second position (I =2) is 1, and I (I =2) is divisible by 1Copy the codeDescription:
- N is a positive integer and does not exceed 15.
State compression DP
With the data range no more than 151515, we can use “state compression DP” for the solution.
A binary number is used to indicate which numbers are currently selected and which are not, so that bit operations can be used to speed things up.
We can get a sense of what state compression means by looking at a specific example:
For example, 000… 2 (0101) 000… 0101) _2 (000… 0101)2 indicates that the numbers with values 111 and 333 have been used, while the node with value 222 has not been used.
Then take a look at some basic operations that can be performed using state compression:
Suppose that the variable statestatestate holds “current number usage”. When we need to check whether the number with value KKK is used, we can use the bit operation a = (state >> k) & 1, To get the binary representation of bit KKK in Statestatestate. If a is 111, the number with the value KKK has been used. If a is 000, the number is not accessed.
define
To consider before
Number, and the current option is
Of all options.
An obvious initialization condition is f[0][0]=1f[0][0] =1f[0][0] =1f[0][0] =1, which means that if we do not consider any number (I =0i = 0I =0), no number is selected (state=0state =0state =0) as a legal solution.
F [I][state]f[I][state]f[I][state]f[I][state]f[I][state]
We can enumerate which number is selected at the current position iii, assuming that the value selected at position III is KKK. First, the value of KKK should meet the following two conditions:
- The KKK bit in StatestatEstate is 111.
- Either KKK is divisible by III, or III is divisible by KKK.
Then, according to the state definition, the value KKK is selected for position III, and the state before decision position III can be directly obtained by bit operation: State & (rope (1 < < (k – 1))) state \ & (\ lnot (1 < < (k – 1))) state & (rope (1 < < (k – 1))), on behalf of the binary representation of the statestatestate first KKK location 000.
The final f[I][state] F [I][state] F [I][state]f[I][state] selects the sum of all valid KKK values for the current position III:
Some details: Since the given value range is [1,n][1,n][1,n], but for implementation convenience, we use statestatestate from right to left of the 000th bit for the value 111 selection, the 111th bit for the value 222 selection… That is, the selected value KKK is offset by −1-1−1.
Code:
class Solution {
public int countArrangement(int n) {
int mask = 1 << n;
int[][] f = new int[n + 1][mask];
f[0] [0] = 1;
for (int i = 1; i <= n; i++) {
// Enumerate all states
for (int state = 0; state < mask; state++) {
// Enumeration position I (last bit) selected value k
for (int k = 1; k <= n; k++) {
// First, k must be 1 in state
if (((state >> (k - 1)) & 1) = =0) continue;
// The value k and position I satisfy any divisible relationship
if(k % i ! =0&& i % k ! =0) continue;
// state & (~(1 << (k-1))) sets the value k in state to zero
f[i][state] += f[i - 1][state & (~(1 << (k - 1)))]; }}}return f[n][mask - 1]; }}Copy the code- Time complexity: a total of n∗ 2NN * 2^ NN ∗2n states need to be transferred. The complexity of each transition is O(n)O(n)O(n) O(n^2 * 2^ N)O(n2∗2n).
- Space complexity: O(n∗2n)O(n * 2^n)O(n∗2n)
State compression DP (optimization)
Through the analysis of the simple shape pressure DP, we found that in the decision of the third position, theoretically we should also use the number of iii.
This is not reflected in the plain pressure DP, which leads to the fact that we still need to run a computational check on all statestatestate (even for states where 111 does not occur iii in binary representation) when deciding on position III.
So we can do enumeration in a different way (using the new state definition and optimizing the transition equation).
define
For the current value is
The number of all options in the.
So that still have f [0] = 1 f [0] = 1 f the initialization conditions [0] = 1, the final answer to f/f (1 < < n) – 1]] [(1 < < n) – 1 f [(1 < < n) – 1).
F [state]f[state]f[state] f[state]f[state]
From the current state
Carry out the departure, check
Every single one of them
As the last value to be selected, this still ensures that the number of schemes is counted “not too heavy”, and since we are paired “from small to large”
To enumerate, and therefore calculate
All other dependent state values must have been computed.
Again, we still need to make sure that the last bit of 111 in Statestatestate is divisible to where it is placed.
Therefore, we need a method to calculate the number of 111 statestatestate, which is implemented using lowBitLowBitlowBit.
The final f[state]f[state]f[state] is the sum of all valid values for the current position:
Code:
class Solution {
int getCnt(int x) {
int ans = 0;
while(x ! =0) {
x -= (x & -x); // lowbit
ans++;
}
return ans;
}
public int countArrangement(int n) {
int mask = 1 << n;
int[] f = new int[mask];
f[0] = 1;
// Enumerate all states
for (int state = 1; state < mask; state++) {
// Count the number of 1's in the current sort.
int cnt = getCnt(state);
// Enumerates the value of the last digit
for (int i = 0; i < n; i++) {
// The value must be 1 in state
if (((state >> i) & 1) = =0) continue;
// The value (I + 1) and the position (CNT) satisfy any divisible relationship
if ((i + 1) % cnt ! =0 && cnt % (i + 1) != 0) continue;
// state & (~(1 << I)) sets the position of the selected value in state to zero
f[state] += f[state & (~(1<< i))]; }}return f[mask - 1]; }}Copy the code- Time complexity: a total of 2n2^n2n states need to be transferred. The complexity of each transition is O(n)O(n)O(n) O(n * 2^n)O(N ∗2n). The overall complexity is O(n∗2n)O(n * 2^n)O(N ∗2n).
- Space complexity: O(2n)O(2^n)O(2n)
conclusion
It is not difficult to find that the two states actually compress DP with exactly the same idea.
However, in the plain pressure DP, we explicitly enumerates the cases considering each length (existence dimension III), while in the shape pressure DP (optimization), we use the length information contained in the number of 111 in Statestatestate.
The last
This is article No.525 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.