Self-built blog address: https://www.bytelife.net, welcome to visit! This article is published simultaneously for the blog. For a better reading experience, I suggest you visit my blog at 👇

The author:
Jeffrey


Link to this article:
https://www.bytelife.net/articles/32340.html


Copyright Notice: All articles in this blog are used unless otherwise stated
BY-NC-SALicense Agreement. Reprint please indicate the source!

Problem: Given an array arr, all values in arr are positive and not duplicated. Each value represents one denomination of the currency, each denomination of the currency can be used in any number of pieces, and given an integer AIM represents the amount of money to be found, how many ways to find out how to change money.

Violent search method

Thought analysis

Given arr={5, 10, 25, 1}, aim=1000.

  • Using 0 pieces of 5 yuan currency, let [10, 25, 1] constitute the remaining 1000 yuan, and the final number of methods is written as ——res1;
  • Using a piece of 5 yuan currency, let [10, 25, 1] constitute the remaining 995 yuan, and the final number of methods is written as ——res2;
  • Using two pieces of 5 yuan currency, let [10, 25, 1] constitute the remaining 990 yuan, and the final number of methods is written as ——res3;
  • Using three pieces of 5 yuan currency, let [10, 25, 1] constitute the remaining 985 yuan, and the final number of methods is written as ——res4;
  • …
  • Using 200 pieces of 5 yuan currency, let [10, 25, 1] constitute the remaining 0 yuan, and the final number of methods is recorded as ——res201;

The res1 and res2… The summation of res201 is the final result.

The specific implementation

Define a recursive function: int process1(arr, index, aim), which returns the total number of methods if the value of 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 taken by violent search method: "+ (endTime-startTime) +"ms"); return result; } public static int process1(int[] arr, int index, int aim) { int res = 0; If (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) { 1:0; } else {for (int I = 0; arr[index] * i <= aim; Res += process1(arr, index + 1, aim-arr [index] * I); } } return res; }

The brute force search method is easy to understand, but it has a lot of repetitive recursive processes in the calculation. For example, if 0 pieces of 5 and 1 piece of 10 have already been used, then process1(arr,2,990) will be followed. If 2 pieces of 5 and 0 pieces of 10 will be used, then process1(arr,2,990) will be followed, so this repeated recursion will cause a lot of time to be wasted.

Memory search method

Thought analysis

Due to violent search method in the presence of large amounts of repeated recursive, so we can use a “memory” is used to store has calculated values, in the subject, using the index value of the currency composition of the rest of the aim of money is one-to-one, so you can use the int memindex said memory array, its elements can be built up in the value of the method of number.

The specific implementation

  • After each process(index,aim) is calculated, the result is put into mem, index and aim form a common key, and the return result is value.
  • To enter a recursive process, first query the key composed of index and aim in mem; if value already exists, use it directly; if not, enter the recursive process again.
public static int process2(int[] arr, int index, int aim, int[][] mem) { int res = 0; If (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) {if (index == arr.length) { 1:0; } else { int memVal = 0; For (int I = 0; int I = 0; arr[index] * i <= aim; I ++) {memVal = mem[index + 1][aim-arr [index] * I]; memVal = mem[index + 1][aim-arr [index] * I]; If (memVal! = memVal! = memVal! = 0) {// Add the number of methods in the memory library to the result res += memVal == -1? 0 : memVal; } else {Res += process2(arr, index + 1, aim-arr [index] * I, mem); }}} // Saves AIM money using INDEX currency to memory mem[INDEX][AIM] = res == 0? -1 : res; return res; }

Dynamic programming method

Thought analysis

If the length of arr is N, a matrix dp with rows of N and columns of aim+1 is generated. DPI means using arr[0]… In the case of arr[I] money, the number of ways to compose the number of money j.

  1. If you don’t use arr[I] currency at all, just use arr[0]… When arr[i-1] currency, the number of methods is dpi-1.
  2. If you use 1 piece of arr[I] and the rest of the money is in arr[0]… Arr [i-1] currency composition, the number of methods is dpi-1].
  3. If you use 2 pieces of arr[I] and the rest of the money is in arr[0]… Arr [i-1] currency composition, the number of methods is dpi-1].
  4. If you use three pieces of arr[I] and the rest of the money is in arr[0]… Arr [i-1] currency composition, the number of methods is dpi-1].
  5. …

The value of DPI is the sum of all the above values. Each location requires enumeration, with a time complexity of O(AIM). Dp has N*aim positions, so the total time complexity is O(N*aim2). The final result value is dpn-1 at the lower right corner of the matrix.

Relationship between memory search method and dynamic programming method

  • The memorized search method is a kind of dynamic programming method.
  • The memorized search doesn’t care about the distance to a recursive path. Just simply heap the recursive process calculated to record, to avoid repeating the recursive process.
  • Dynamic programming method is to stipulate the calculation order of each recursive Haocheng, and carry out the calculation once, and the subsequent calculation process strictly depends on the previous calculation process.
  • Both of them are spatial-time-exchange methods, and also have enumeration process. The difference is that dynamic programming specifies the calculation order, while memory search does not.

What is a dynamic programming approach

  • In essence, the application space is used to record the calculation process of each violent search, and the next time the result is needed, it is directly used instead of repeated recursive process.
  • Dynamic programming specifies the calculation order of each recursive state, which is calculated in turn. From simple to complex, in order of calculation.

The specific implementation

Public static int process3(int[] arr, int aim) {int[][] dp = new int[arr.length][aim + 1]; for (int i = 0; i < dp.length; i++) { dp[i][0] = 1; If (I == 0) {// if (I == 0) {// if (I == 0) {// if (I == 0) {// if (I == 0) {// if (I == 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 entries in dp[I -1] for (int k = 0; k * arr[i] <= j; k++) { temp += dp[i - 1][j - k * arr[i]]; } dp[I][j] = temp; }}} return dp[arr. Length - 1][aim]; }

Re-optimization of dynamic programming method

Thought analysis

As the execution sequence of dynamic programming method is strictly defined, it is possible to optimize the algorithm further. For the previous problem, we need to enumeratedp[i-1][j-k*arr[i]](k = 1, 2, 3…). And with thedp[i-1][j]And then you add up, actuallydp[i-1][j-k*arr[i]](k = 1, 2, 3…). The sum of omega is omegadp[i][j-arr[i]].



Therefore, it can be simplified as:dp[i][j] = dp[i][j-arr[i]] + dp[i-1][j]This completely eliminates the enumeration process. The time goes 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) {int[][] dp = new int[arr.length][aim + 1]; for (int i = 0; i < dp.length; i++) { dp[i][0] = 1; // 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]; }}} return dp[arr. Length - 1][aim]; }

Spatial 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. This is achieved by reading and modifying the element value of the vector itself. The modified code looks like this:

Public static int process5(int[] arr, int aim) {// create dp int[] dp = new int[aim + 1]; for (int i = 0; i < arr.length; i++) { dp[0] = 1; // 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]]; }}} return dp[aim]; }

Comparison of running speed of various calculation methods

All of the above implementation code is added to record the start and end time of the algorithm. By running the test, we get the following results:

  • As you can see, the brute force search method is undoubtedly the slowest, due to the large number of repeated recursive processes.
  • The memorized search method is more efficient because it avoids repeated recursion.
  • Through the optimized dynamic programming method, we can see that in my measured environment, the running time is nearly 0ms, which can be said to be very fast.

The general process of violence recursion optimization into dynamic programming methods

  1. Realize violence recursive method;
  2. See which parameters represent recursive processes in the brute force search method’s functions.
  3. Once the parameters representing the recursive process are found, the implementation of the memorized search method is very easy.
  4. By analyzing the dependent path of memorized search, the dynamic programming is realized.
  5. According to the memorization search method, the dynamic programming method is changed to see if it can be simplified. If it can be simplified, the dynamic programming method with lower time complexity can be realized.

Key points of dynamic programming method

  1. Principle of optimization: that is, optimal substructure properties. An optimal strategy has the property that, regardless of past states and decisions, the remaining decisions must constitute the optimal policy for the state resulting from 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 optimal substructure property.
  2. No aftereffect: refers to the benefits of a decision in a state, only related to the state and the decision, not the path to the state.
  3. 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 the dynamic programming algorithm.