Self-built blog address: bytelife.net, welcome visit! For a better reading experience, I suggest you go to my blog 👇
Link to this article: bytelife.net/articles/32… Copyright Notice: All articles on this blog are licensed BY-NC-SA unless otherwise stated. Reprint please indicate the source!
Problem: Given an array arR, all values in arR are positive and not repeated. Each value represents a denomination of currency, each denomination of currency can be used any note, and given an integer aim represents the amount of money to find, how many ways to find the money.
Violence search method
Thought analysis
Given arR ={5, 10, 25, 1}, aim=1000.
- Take 0 pieces of 5 yuan currency, let [10, 25, 1] form the remaining 1000 yuan, the final method number is written ——res1;
- Take a 5 yuan note and let [10, 25, 1] make up the remaining 995 yuan. The final method number is written as ——res2.
- Take two five-dollar bills and let [10, 25, 1] make up the remaining 990 yuan. The final method is written as ——res3.
- Take three five-dollar bills and let [10, 25, 1] make up the remaining 985 yuan. The final method is written as ——res4.
- …
- Take 200 pieces of 5 yuan currency, let [10, 25, 1] form the remaining 0 yuan, the final method number is written ——res201;
The res1 and res2… The sum of RES201 is the final result.
The specific implementation
Define the recursive function int process1(ARR, index, AIM) that returns the total number of methods if arR [index… n-1] is used to form AIM.
public static int coins1(int[] arr, int aim) {
long startTime = System.currentTimeMillis();
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
int result = process1(arr,0,aim);
long endTime = System.currentTimeMillis();
System.out.println("Time spent on violent search methods:" + (endTime - startTime) +"ms");
return result;
}
public static int process1(int[] arr, int index, int aim) {
int res = 0;
// Determine if all denominations have been counted
if (index == arr.length) {
// Determine whether the total amount of money has been reached at the time of the recursive call. If so, add 1 to the total number of methods
res = aim == 0 ? 1 : 0;
} else {
// Loop through the current denomination of I notes
for (int i = 0; arr[index] * i <= aim; i++) {
When using the current denomination, use other currencies to make up the rest of the money
res += process1(arr, index + 1, aim - arr[index] * i); }}return res;
}
Copy the codeThe brute force search method is easier to understand, but it involves a lot of repeated recursion in the calculation. Process1 (ARr,2,990) will be asked if it has already used 0 fives and 1 10 bills, and process1(ARr,2,990) will be asked if it has used 2 fives and 0 10 bills, so this repeated recursive operation will cause a lot of time waster.
Memory search method
Thought analysis
Since there is a lot of repeated recursion in the violent search method, we can use a “memory bank” to store the calculated values. In this case, the values of the remaining AIM money made up of the index currency are one-to-one, so we can use the int mem[index][AIM] array to represent the memory bank. The element value is the number of methods that can be composed.
The specific implementation
- Every time a process(index, AIM) is calculated, the result is put into MEM, index and AIM form a common key, and the result is returned as value.
- To enter a recursive process, the key composed of index and AIM is first queried in MEM. If value already exists, it is directly used; if not, the recursive process is entered.
public static int process2(int[] arr, int index, int aim, int[][] mem) {
int res = 0;
// Determine if all denominations have been counted
if (index == arr.length) {
// Determine whether the total amount of money has been reached at the time of the recursive call. If so, add 1 to the total number of methods
res = aim == 0 ? 1 : 0;
} else {
int memVal = 0;
// Loop through the current denomination of I notes
for (int i = 0; arr[index] * i <= aim; i++) {
// Get the amount of money left in the memory when I index coins are used
memVal = mem[index + 1][aim - arr[index] * i];
// Check that there are records in the memory store
if(memVal ! =0) {
// Add the number of methods in the memory to the result
res += memVal == -1 ? 0 : memVal;
} else {
When using the current denomination, use other currencies to make up the rest of the money
res += process2(arr, index + 1, aim - arr[index] * i, mem); }}}// Store the result of composing AIM money with index currency in memory
mem[index][aim] = res == 0 ? -1 : res;
return res;
}
Copy the codeDynamic programming method
Thought analysis
If the length of arR is N, the matrix dp with N rows and AIM +1 columns is generated. Dp [I][j] is used in arr[0]… Arr [I] in the case of money, the number of methods that make up the money number j.
- If you don’t use arR [I] currency at all and just use ARR [0]… In arR [i-1] currency, the method number is DP [i-1][J].
- If you use 1 arR [I] currency, the remaining money is used in ARR [0]… Arr [i-1] consists of currency, and the number of methods is DP [i-1][J-1 * ARR [I]].
- If two arR [I] coins are used, the remaining money is used in ARR [0]… Arr [i-1] consists of currency, and the number of methods is DP [i-1][J-1 * ARR [I]].
- If three arR [I] coins are used, the remaining money is used in ARR [0]… Arr [i-1] consists of currency, and the number of methods is DP [i-1][J-1 * ARR [I]].
- …
The value of dp[I][j] is the sum of all the above values. Enumeration is required for each location, and the time complexity is O(AIM). Dp has a total of N* AIM positions, so the total time complexity is O(N*aim2). The final result value is dp[n-1][AIM] at the bottom right corner of the matrix.
The relation between memory search method and dynamic programming method
- Memorization search method is a kind of dynamic programming method.
- Mnemonic search doesn’t care how far it takes to reach a recursive path. Simply heap the calculated recursive process to record, avoid repeating the recursive process.
- The dynamic programming method is to specify the calculation sequence of each recursive Hocheng, one calculation, the following calculation process strictly depends on the previous calculation process.
- Both of them are spatial-temporal methods, as well as enumeration processes. The difference is that dynamic programming prescribes the calculation order, while memory search does not.
What is the dynamic programming approach
- The essence is to use the application space to record the calculation process of each violent search, the next time to use the results directly, rather than repeat the recursive process.
- Dynamic programming specifies the order in which each recursive state is calculated. From simple to complex, in order.
The specific implementation
public static int process3(int[] arr, int aim) {
// Create the dp matrix
int[][] dp = new int[arr.length][aim + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][0] = 1; // There is no need to use any currency, but only one
if (i == 0) {
// arr[0] = arr[0] = arr[0] = arr[0
for (int j = 0; j < dp[i].length; j++) {
dp[i][j] = j % arr[i] == 0 ? 1 : 0; }}else {
for (int j = 1; j < dp[i].length; j++) {
int temp = 0;
// enumerate the number of methods that make up the remaining amount of money in dp[i-1] after using k arr[I] coins
for (int k = 0; k * arr[i] <= j; k++) {
temp += dp[i - 1][j - k * arr[i]];// add method number} dp[i][j] = temp; }}}// Returns the bottom right corner of the dp matrix
return dp[arr.length - 1][aim];
}
Copy the codeReoptimization of dynamic programming methods
Thought analysis
Because the execution sequence of dynamic programming method has strict rules, it is possible to further optimize the algorithm. For the previous problem, we need enumerationdp[i-1][j-k*arr[i]](k = 1, 2, 3…). And with thedp[i-1][j]Plus, actuallydp[i-1][j-k*arr[i]](k = 1, 2, 3…). The sum of omega is omegadp[i][j-arr[i]].
dp[i][j] = dp[i][j-arr[i]] + dp[i-1][j]Thus omitting the enumeration process entirely. Time complexity from O(N)Aim2) to O (Naim)
The specific implementation
The optimized code is implemented as follows:
public static int process4(int[] arr, int aim) {
// Create the dp matrix
int[][] dp = new int[arr.length][aim + 1];
for (int i = 0; i < dp.length; i++) {
dp[i][0] = 1; // There is no need to use any currency, but only one
for (int j = 1; j < dp[i].length; j++) {
if (i == 0) {
dp[i][j] = j % arr[i] == 0 ? 1 : 0;
} else if(j >= arr[i]){
dp[i][j] = dp[i][j - arr[i]] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j]; }}}// Returns the bottom right corner of the dp matrix
return dp[arr.length - 1][aim];
}
Copy the codeSpatial optimization of dynamic programming methods
We can see that after optimization of the dynamic programming method is already very satisfactory, but its space waste is very serious, we found that the dynamic programming method is strict matrix from top to bottom and from left to right in the direction of the order, so every time the real calculation formula is only needed on the current line with the current row of a line, So we can actually reduce the original dp two-dimensional matrix to a one-dimensional vector. We do this by reading and modifying the element values of the vector itself, and the modified code looks like this:
public static int process5(int[] arr, int aim) {
// Create the dp vector
int[] dp = new int[aim + 1];
for (int i = 0; i < arr.length; i++) {
dp[0] = 1; // There is no need to use any currency, but only one
for (int j = 1; j < dp.length; j++) {
if (i == 0) {
dp[j] = j % arr[i] == 0 ? 1 : 0;
} else if(j >= arr[i]){ dp[j] += dp[j - arr[i]]; }}}// returns the end element of the dp vector
return dp[aim];
}
Copy the codeRunning speed comparison of various calculation methods
All of the above implementation codes were added to record the start and end time of the algorithm. We ran the test and got the following results:
- As you can see, the violence search method is undoubtedly the slowest because of the large amount of repeated recursive process.
- The mnemonic search method is more efficient because it avoids repeated recursion.
- It can be seen from the optimized dynamic programming method that in my measured environment, the running time is nearly 0ms, which can be said to be very fast.
Violent recursion optimization into a dynamic programming method of the general process
- Implementation of violence recursive method;
- See which parameters represent the recursive process in the brute force search function.
- Once the parameters that represent the recursive process are found, the implementation of the mnemonized search method is very easy.
- Dynamic programming is realized by analyzing the dependent path of mnemonic search.
- According to the mnemonic search method to change the dynamic programming method, and then see if it can be simplified, if it can be simplified, it can also realize the dynamic programming method with lower time complexity.
Key points of dynamic programming approach
- Principle of optimization: namely, the properties of optimal substructures. An optimization strategy has the property that, regardless of the past state and decision, the remaining decisions must constitute the optimal strategy for the state formed by the previous decision. Simply put, the substrategy of an optimization strategy is always optimal. If a problem satisfies the optimization principle, it is considered to have the property of optimal substructure.
- No aftereffect: The benefits of a decision made in a state, related only to the state and the decision, independent of the path to the state.
- Overlapping of subproblems: Dynamic programming improves the violent search algorithm with exponential time complexity to one with polynomial time complexity. The key is to solve the redundancy, which is the fundamental purpose of dynamic programming algorithm.
If you need to buy this course, you can use the blogger’s promo code: Adg00aI to get 10 yuan discount.