Dynamic programming
What is dynamic programming and how do we describe it?
Dynamic programming algorithms are usually based on a recursive formula and one or more initial states. The solution of the current subproblem is derived from the solution of the previous subproblem. Using dynamic programming to solve problems requires only polynomial time complexity, so it is much faster than backtracking, brute force, etc.
Now let’s take a look at the basics of DP through an example.
First, we need to find the optimal solution for one state, and then with the help of that, we need to find the optimal solution for the next state.
What does “state” stand for and how to find it?
The state is used to describe the solution of the subproblem of the problem.
If we have several $1, $3 and $5 coins, how can we make $11 with the least amount of coins? (On the surface, this problem can be solved by greedy algorithm, but greedy algorithm can not guarantee the solution, such as 1 yuan to 2 yuan.)
First of all, let’s think about a problem, how to make up I yuan with the least coins (I <11)? Why do you ask?
Two reasons:
- When we have a big problem, it is customary to reduce the size of the problem to a smaller size so that it can be easily analyzed and discussed.
- This problem with smaller scale is homogeneous with the original problem, except for the smaller scale, everything else is the same, in essence it is the same problem **(the problem with smaller scale is actually a sub-problem of the original problem). 六四事件
Well, let’s start with the smallest I. When I is equal to 0, how many coins do we need to get to 0 yuan. Since 1, 3, and 5 are all greater than 0, so there’s nothing less than 0, we need at least 0 coins to get 0 yuan.
So let’s say d of I is equal to j to get at least j coins. So we’ve got d of 0 is equal to 0, which means we need at least 0 coins to get to 0 yuan.
When I is equal to 1, there are only 1 dollar coins available, so we pick up a 1 dollar coin, and we just have to make up 0 dollars, and we already know the answer to that, which is d of 0 is equal to 0. So d(1)=d(1-1)+1=d(0)+1=0+1=1.
When I =2, there are still only 1 coins available, so I pick up a 1 coin, and then I just need to make up 2-1=1 yuan (remember to use the minimum number of coins), and I already know the answer. So the d (2) = d (2, 1) (1) + 1 + 1 = d = 1 + 1 = 2.
When I =3, there are two kinds of coins we can use: 1 yuan coins and 3 yuan coins (5 yuan coins are still useless, because you need to make up 3 yuan coins! 5 yuan is too much. Since there are two kinds of coins I can use, I have two options. If I take a $1 coin, my goal becomes: the minimum number of coins needed to make up $3-1= $2. D (3) = d (3, 1) (2) + 1 + 1 = d = 2 + 1 = 3.
So this scenario says, I take three one-dollar coins; In the second scenario, I pick up a $3 coin, and my goal becomes: the minimum number of coins needed to get $3-3= $0. So d(3)=d(3-3)+1=d(0)+1=0+1=1. This scenario says, I take a 3 dollar coin.
Okay, which of these two plans is better? Remember we need the minimum number of coins to get three dollars. So d of 3 is equal to 1. How did that happen? D (3)=min{d(3-1)+1, d(3-3)+1}
From the above text, we will draw out two very important concepts in dynamic programming: states and state transition equations.
Define states according to subproblems. You find the subproblem, and the state comes to the surface. So the problem that we’re going to solve, we’re going to solve it in this state: d(11), the minimum number of coins needed to make 11 dollars. What is the transition equation? Since we use d(I) to represent the state, the state transition equation naturally includes D (I). The equation containing state D (I) above is: d(3)=min{d(3-1)+1, d(3-3)+1}. Yes, it’s a transition equation, which describes how states move from one state to another. And of course, we’re going to abstract it,
import java.util.*;
/ * * *@author SJ
* @date2020/10/20 * /
public class Coins {
** If we have several coins of 1 yuan, 3 yuan and 5 yuan, how can we make 11 yuan with the minimum coins?
public static void main(String[] args) {
int[] coins = {1.3.5};
System.out.println(poolMoneyByCoin(coins, 11));
poolMoneyByCoin2(coins, 11);
}
public static int poolMoneyByCoin(int[] coins, int money) {
int[] d = new int[money + 1];
d[0] = 0;
for (int i = 1; i <= money; i++) {
d[i] = i;
for (int j = 0; j < coins.length; j++) {
// If we coin[j] to make the current solution better than the previous one
if (coins[j] <= i && d[i - coins[j]] + 1 < d[i])
d[i] = d[i - coins[j]] + 1; }}return d[money];
}
// Try output schemes
public static void poolMoneyByCoin2(int[] coins, int money) {
Map<Integer, List<Integer>> plan = new HashMap<>();
plan.put(0.new ArrayList<>());
// plan.get(0).add(0);
// int[] d = new int[money + 1];
// d[0] = 0;
for (int i = 1; i <= money; i++) {
plan.put(i, new ArrayList<>());
for (int k = 0; k < i; k++) {
plan.get(i).add(1);
}
for (int j = 0; j < coins.length; j++) {
// If we coin[j] to make the current solution better than the previous one
if (coins[j] <= i && plan.get(i - coins[j]).size() + 1 < plan.get(i).size()) {
plan.get(i).clear();
plan.get(i).addAll(plan.get(i - coins[j]));
plan.get(i).add(coins[j]);
}
}
}
System.out.println("The minimum number of coins you can get is + plan.get(money).size() + "In this case, the scheme is:"+ plan.get(money).toString()); }}Copy the codeResults:
"C: \ Program Files \ Java \ jdk1.8.0 _131 \ bin \ Java exe".3The minimum number of coins you get is zero3At this point, the scheme is: [5.5.1]
Process finished with exit code 0
Copy the codeWe’re going to introduce a new term called recursion to connect states.
A sequence has N numbers: A[1],A[2]… ,A[N], find the length of the longest non-descending subsequence. (LIS: Longest increasing subsequence)
As we said above, faced with such a problem, we must first define a “state” to represent its sub-problems and find its solution. Note that most of the time, a state is related only to the state that precedes it, not to the state that follows it.
That is, starting from index=0, calculate the length of the longest increasing subsequence with ARr [index] as the end point of the longest increasing sequence one by one and save it in dp[index]. When calculating the length of the longest increasing sequence with any index as the end point, traverse the maxLength of all the preceding elements. Find the maxLength value of the element arr[I]<arr[index], add ARR [index] to this sequence to form the longest increasing subsequence ending in ARr [index], and so on, when the index reaches the end, the traversal of the length of all subsequences ends. Scan the entire array dp[] and the maximum value is the length of the maximum increasing subsequence (the last element index is not necessarily the end element of the oldest sequence, i.e. the longest increasing subsequence may be in the middle of a sequence).
Dynamic programming:
① Create a dynamic programming array to preserve the results of each calculation, here only need a one-dimensional array dp[n];
② First calculate the value of the first position in DP [], that is, DP [0], that is, the maximum length of the longest increasing subsequence ending at ARR [0] is 1;
③ Calculate the value of each position in DP [] from front to back; Note the use of recursive relationships;
(4) Scan DP [], and the maximum value inside is the result obtained;
/ * * *@author SJ
* @date2020/10/20 * /
public class LIS {
// A sequence has N numbers: A[1],A[2]... ,A[N], find the length of the longest non-descending subsequence.
public static void main(String[] args) {
int[] nums = {1.4.2.5.3};
System.out.println(findLIS(nums, 5));
}
public static int findLIS(int[] nums, int n) {
int[] dp = new int[nums.length];
dp[0] = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = dp[i - 1];
for (int j = 0; j < i; j++) {
if (nums[j] <= nums[i] && dp[j] + 1 > dp[i])
dp[i] = dp[j] + 1; }}return dp[n - 1]; }}Copy the code"C: \ Program Files \ Java \ jdk1.8.0 _131 \ bin \ Java exe"
3
Process finished with exit code 0
Copy the codeThe undirected graph G has N nodes (1<N<=1000) and some edges, each of which has a positive weight value. Find the shortest path from node 1 to node N, or output that does not exist.
Tip: In each step, for nodes that have not been calculated, and for nodes that have calculated the shortest path from node 1 to it, if they have edges, calculate the shortest path from node 1 to the uncalculated node.
import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/ * * *@author SJ
* @date2020/10/21 * /
public class NoPointGraph {
public static void main(String[] args) {
// The adjacency matrix stores weights
int V = 6;
int[][] nums = new int[V + 1][V + 1];
getShortestPath(nums);
}
// The shortest path from node 1 to n
public static void getShortestPath(int[][] adjacent) {
// Initialize the adjacency matrix to store the maximum value
for (int i = 0; i < adjacent.length; i++) {
for (int j = 0; j < adjacent[i].length; j++) { adjacent[i][j] = Integer.MAX_VALUE; }}/ / input side
// Scanner scanner = new Scanner(System.in);
// system.out. println(" Input number; ") );
// int V = scanner.nextInt();
int V = 6;
// system.out. println(" input edge number ");
int E = 9;
// int E = scanner.nextInt();
// system.out. println(" Input the weights of two points and edges ");
// Store the information in the adjacency matrix, row 0, column 0
// for (int i = 1; i <= E; i++) {
// int x = scanner.nextInt();
// int y = scanner.nextInt();
// int weight = scanner.nextInt();
// adjacent[x][y]=weight;
// adjacent[y][x]=weight;
/ /}
adjacent[1] [2] = 1;
adjacent[2] [1] = 1;
adjacent[1] [3] = 12;
adjacent[3] [1] = 12;
adjacent[2] [3] = 9;
adjacent[3] [2] = 9;
adjacent[2] [4] = 3;
adjacent[4] [2] = 3;
adjacent[3] [5] = 5;
adjacent[5] [3] = 5;
adjacent[4] [3] = 4;
adjacent[3] [4] = 4;
adjacent[4] [5] = 13;
adjacent[5] [4] = 15;
adjacent[4] [6] = 15;
adjacent[6] [4] = 15;
adjacent[5] [6] = 4;
adjacent[6] [5] = 4;
// Define two collections to store unaccessed nodes and already accessed nodes
Set<Integer> visited = new HashSet<>(V);// The optimal solution point has been determined
Set<Integer> unVisited = new HashSet<>(V);//// has not found the optimal solution point
// Save the local optimal solution
int[] dp = new int[V + 1];
// Initializes the locally optimal solution
for (int i = 1; i <= V; i++) {
unVisited.add(i);
dp[i] = Integer.MAX_VALUE;
}
dp[1] = 0;
visited.add(1);
unVisited.remove(1);
If so, calculate the minimum value of dp[m]+adjcent[m][I] and store it in dp[I].
int currentIndex = 1;
while(unVisited.size() ! =0) {
int tempMin = Integer.MAX_VALUE;// Find the shortest path between currentIndex and I
int tempMinIndex = -1;// Subscript I when current is closest to I
for (Integer i : unVisited) {
// If the current node has an edge attached to it
if(adjacent[currentIndex][i] ! = Integer.MAX_VALUE) {// Update the shortest path constantly
if (dp[currentIndex] + adjacent[currentIndex][i] < dp[i])
dp[i] = dp[currentIndex] + adjacent[currentIndex][i];
}
if(dp[i] < tempMin) { tempMin = dp[i]; tempMinIndex = i; } } visited.add(tempMinIndex); unVisited.remove(tempMinIndex); currentIndex = tempMinIndex; } System.out.println(Arrays.toString(dp)); }}Copy the code"C: \ Program Files \ Java \ jdk1.8.0 _131 \ bin \ Java exe". [0.0.1.8.4.13.17]
Process finished with exit code 0
Copy the codeDijkstra algorithm for single source shortest path:
1. Adjcent [][] Store the weights of corresponding points ([I,j] and [j, I] should be stored)
2. Visited sets: Store the points that have already found the shortest path (note: this is not the point visited, but the point that has already found the shortest path)
Unvisited Sets: Stores points that have not yet found the shortest path
4. Dp array, which stores the optimal solution of the sub-problem
dp[1]=0; (The above procedure is calculated from subscript 1)
Procedure: Initialize each value of the adjacency matrix and each value in the DP array to infinity, using interger.max_value instead
Add point 1 to the visited set, and add points 2-5 to the Unvisited set
Define three temporary variables:
- CurrentIndex: the point of the subproblem where the optimal solution was found last time and the next optimal solution is found.
- TempMin: The shortest distance between the current currentIndex and the point directly connected to it
- TempMinIndex: Point with the shortest distance from currentIndex
When the length of the Unvisited collection is not 0, perform the following steps:
Through the unvisited set, remember that the point traversed at this time is I
-
Search the point X directly connected to currentIndex in Unvisited (now currentIndex has found the optimal solution and saved it in dp array)
If (dp[currentIndex]+adjcent[currentIndex][x] + dp[x] +adjcent[currentIndex][x] + DP [x])
In this process, the minimum dp[I] is found, that is, the shortest path among the points where the optimal solution is not determined, and this point is denoted as tempMinIndex and the shortest distance as tempMin.
-
After completing the above steps, the optimal solution of tempMinIndex has been found, and tempMinIndex is written into the Visited set and removed from the Unvisited set. Update currentIndex to tempMinIndex.
-
Continue from the beginning of the step until the loop condition is not satisfied.
There are N by M cells in the plane, and each cell holds a certain number of apples. You start at the upper left corner of the grid, each step can only go down or to the right, each time you go to the grid to collect the apples, so that, how many apples can you collect.
Solving this problem is almost the same as solving any other DP problem. The first step is to find the “state” of the problem, the second step is to find the “state transition equation”, and then basically the problem is solved.
First of all, what is the “state” in this problem? It is important to note that there are at most two ways to reach a cell: from the left (except for the first column) and from above (except for the first row). So in order to figure out how many apples we can collect if we get to the current cell, we have to look at how many apples we can collect if we get to the current cell. (It’s a little convoluted, but the essence of this statement is actually the key to DP: if you want to solve a problem, you should solve a subproblem first.)
The state S[I][j] is the maximum number of apples we can collect when we reach the cell (I, j). Then, the state transition equation is as follows:Copy the codeS [j] = [I] A [I] [j] + Max {s [j], [I - 1] if I > 0, s [1] [I] if j > 0}, including A [I] [j] (I, j) is the number of the point of appleCopy the codeS[I][J] have two kinds of calculation: 1. For each row, calculate from left to right, and then process line by line from top to bottom; 2. 2. For each column, work from top to bottom, then work from left to right column by column. The purpose of this is so that when calculating S[I][j], S[i-1][j] and S[I][j-1] have been calculated.
import java.util.Arrays;
/ * * *@author SJ
* @date2020/10/21 * /
public class PickUpApples {
public static void main(String[] args) {
pickUpApples(3.3);
}
public static void pickUpApples(int M, int N) {
int[][] apples;
apples = new int[] [] {{1.4.4}, {5.3.2}, {3.5.1}};
int[][] dp = new int[M][N];
dp[0] [0] = apples[0] [0];
// Initialize the first row and column
for (int i = 1; i < M; i++) {
dp[0][i] = dp[0][i - 1] + apples[0][i];
}
for (int i = 1; i < N; i++) {
dp[i][0] = dp[i - 1] [0] + apples[0][i];
}
// Transfer equation
for (int i = 1; i < M; i++) {
for (int j = 1; j < N; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + apples[i][j]; }}for (int[] ints : dp) { System.out.println(Arrays.toString(ints)); }}}Copy the codeOutput dp array:
"C: \ Program Files \ Java \ jdk1.8.0 _131 \ bin \ Java exe". [1.5.9]
[5.8.11]
[9.14.15]
Process finished with exit code 0
Copy the codeDP problem with additional conditions.
An undirected graph G has N nodes with positive weights on its edges.
You start at node 1, and you start with M dollars. If you pass node I, you spend S[I] dollars (think of it as a toll). If you don’t have enough money, you can’t go through that node. Given this constraint, find the shortest path from node 1 to node N. Or output that the path does not exist. If there are multiple shortest paths, output the one that costs the least. Limit: 1<N<=100; 0<=M<=100 ; For each I, 0<=S[I]<=100; As we can see, if there are no additional constraints (charging at nodes, not paying enough), then the problem is just like the classic Dijkstra problem (finding the shortest path between two nodes). In the classic Dijkstra problem, we use a one-dimensional array to hold the length of the shortest path from the start node to each node, that is, M[I] represents the length of the shortest path from the start node to node I. In this case, however, we also want to keep information about how much money we have left. Therefore, it is natural to extend a one-dimensional array to a two-dimensional array. M[I][j] represents the shortest path length from the start node to node I, and the remaining j element. In this way, we reduce the problem to the original path of finding the problem. In each step, to find the shortest path, we find that it can reach the next state of unmarked (I, j), it is marked as visited (after no longer access the node), and are able to reach the nodes of the shortest path, combined with the current edge weights later found minimum corresponding path, namely for the nodes of the shortest path. (Writing is really convoluted, I suggest drawing a picture will be a lot clearer). Repeat the above steps until all nodes have been accessed (the access is not required to go through it, for example, there is a node that is expensive, you do not have enough money to go through it, but you have already visited it). The minimum value in Min[n-1][j] is the answer to the question (if there are multiple minima, If there are multiple shortest paths, choose the path with the greatest j, i.e., the shortest path with the greatest amount of money left.
Dp array to store the shortest path and minimum cost (how much money is left) two values, I
In the case of the same shortest paths, if the current path costs less (and has more money left) then update, and each time you choose the next node, decide whether you have enough money.
The code above adds a little extra judgment:
import java.util.*;
/ * * *@author SJ
* @date2020/10/21 * /
public class ShortestPath2 {
public static void main(String[] args) {
/** ** You start at node 1, and you start with M yuan. If you pass node I, * then you have to spend S[I] dollars (think of this as a toll). If you don't have enough money, you can't go through that node. * Find the shortest path from node 1 to node N under such constraints. Or output that the path does not exist. If there are multiple shortest paths *, output the one with the least amount of money. * /
// Suppose there are 6 points and 9 edges
int[][] adjacent=new int[7] [7];
// Initialize the adjacency matrix to store the maximum value
for (int i = 0; i < adjacent.length; i++) {
for (int j = 0; j < adjacent[i].length; j++) {
adjacent[i][j] = Integer.MAX_VALUE;
}
}
adjacent[1] [2] = 1;
adjacent[2] [1] = 1;
adjacent[1] [3] = 2;
adjacent[3] [1] = 2;
adjacent[2] [3] = 9;
adjacent[3] [2] = 9;
adjacent[2] [4] = 3;
adjacent[4] [2] = 3;
adjacent[3] [5] = 5;
adjacent[5] [3] = 5;
adjacent[4] [3] = 2;
adjacent[3] [4] = 2;
adjacent[4] [5] = 13;
adjacent[5] [4] = 15;
adjacent[4] [6] = 15;
adjacent[6] [4] = 15;
adjacent[5] [6] = 4;
adjacent[6] [5] = 4;
// Total cost, starting with index 1
int[] cost={0.1.3.1.4.5.6};
getShortestPath(adjacent,cost,30);
}
// The shortest path from node 1 to n
public static void getShortestPath(int[][] adjacent, int[] cost,int property) {
int V = adjacent.length-1;// The number of points, again from the index 1
// Define two collections to store unaccessed nodes and already accessed nodes
Set<Integer> visited = new HashSet<>(V);// The optimal solution point has been determined
Set<Integer> unVisited = new HashSet<>(V);//// has not found the optimal solution point
Dp [I][0] dp[I][1] dp[I][1
int[][] dp = new int[V + 1] [2];
// Initializes the locally optimal solution
for (int i = 1; i <= V; i++) {
unVisited.add(i);
dp[i][0] = Integer.MAX_VALUE;
dp[i][1] = 0;
}
dp[1] [0] = 0;
dp[1] [1] = property-cost[1];
property-=cost[1];
visited.add(1);
unVisited.remove(1);
int currentIndex = 1;
while(unVisited.size() ! =0) {
int tempMin = Integer.MAX_VALUE;// Find the shortest path between currentIndex and I
int tempMinIndex = -1;// Subscript I when current is closest to I
int tempNodeCost=Integer.MIN_VALUE;
for (Integer i : unVisited) {
// If the current node has an edge attached to I and there is enough money left to go through the node
if(adjacent[currentIndex][i] ! = Integer.MAX_VALUE&&property>=cost[currentIndex]) {// Continuously update the shortest path path is shorter than it is directly updated
if (dp[currentIndex][0] + adjacent[currentIndex][i] < dp[i][0])
{dp[i][0] = dp[currentIndex][0] + adjacent[currentIndex][i];
dp[i][1]=dp[currentIndex][1]-cost[i];
}
// The path is the same length, the cost is less than it update
else if (dp[currentIndex][0] + adjacent[currentIndex][i] == dp[i][0]&&dp[currentIndex][1]-cost[i]>dp[i][1])
{ dp[i][0] = dp[currentIndex][0] + adjacent[currentIndex][i];
dp[i][1]=dp[currentIndex][1]-cost[i]; }}// The value of the node that is connected to the vertex currentIndex has been updated, and the minimum dp value is found from all the points that have not determined the optimal solution
// Is updated to the next node
if (dp[i][0]<tempMin||(dp[i][0]==tempMin&&dp[i][1]>tempNodeCost)){
tempMin=dp[i][0];
tempMinIndex=i;
tempNodeCost=dp[i][1];
}
}
visited.add(tempMinIndex);
unVisited.remove(tempMinIndex);
currentIndex=tempMinIndex;
}
for (int[] ints : dp) { System.out.println(Arrays.toString(ints)); }}}Copy the code"C: \ Program Files \ Java \ jdk1.8.0 _131 \ bin \ Java exe"
[0.0]
[0.29]
[1.26]
[2.28]
[4.24]
[7.23]
[11.17]
Process finished with exit code 0
Copy the code