java algorithm dynamic programming

java-Dynamic Programming Algorithms Learning Notes

Original: java-Dynamic Programming Algorithms Learning Notes-huster-stl-Blog Park (cnblogs.com)

 

Dynamic programming is a branch of operational research and a mathematical method to solve the optimization of decision process. Dynamic planning often appears as a test question in written interviews, among which the simpler DP questions should be solved with 100% confidence.

Dynamic Programming Definition

Dynamic programming is actually the general name of a category of topics, not a fixed algorithm. The meaning of dynamic planning is to solve the whole problem by adopting a recursive (or divide-and-conquer) strategy and by solving the sub-problems of a big problem. The core idea of dynamic planning is to cleverly divide the problem into several sub-problems and compute the sub-problems to get the solution of the overall problem. Subproblems can be split into more subproblems to solve the required problems in a recursive and iterative way.

Solving Core of Dynamic Planning

The core of dynamic programming is divided into two steps:

  1. Step 1: Definition of state
  2. Step 2: Definition of the state transfer equation

Here, we use the word status instead of the word problem to avoid confusion. The meaning of "question" is similar: the concept of title, the content to be solved, the question in the stem. The state represents our analytical transformation of the problem in solving it.

Step 1: Definition of state

Some problems are too abstract or too verbose to interfere with our way of thinking. What we need to do is to transform the problems in the main topic (in other words, meaning unchanged). A case that translates into a solution to a series of similar problems, such as:

Topic: Find the sum of the largest continuum in a sequence.

We want to turn this original problem into:

State Definition: Fk is the maximum sequence sum before the k term, and finds the maximum value in F1-FN.

By changing the way of expression, we clearly find the solution to the problem. How to find the maximum value in F1-FN is the key part to solve the original problem. The process of transforming the original problem into another form of expression described above is called the definition of state. Such a state definition gives a similar general solution, converting a previously confused problem into one that can be solved.

Step 2: Definition of the state transfer equation

After defining the state, it is natural to think of solving the maximum value in F1-FN. This is also the role of the state definition, which allows us to turn an overall problem into a series of problems. Step 2: The definition of the state transfer equation tells us how to solve a problem. For those problems that have been converted into a series of problems, the focus is on how we can get the next item with the information of the previous item or items. This idea of changing from the optimal sub-state to the next optimal state is the core of dynamic planning. (
For the example Title above, the definition of the state transfer equation should be:

Fk=max{Fk-1+Ak,Ak} 
Fk is the sum of the first k terms, and Ak is the value of the first k terms

After careful consideration, we can conclude that the maximum subsequence of the first k terms is the largest subsequence of the first k-1 terms, and that the sum of the Fk and the K terms, or that the K terms are larger. If you still can't understand this principle and suggest calculating it yourself with calculating paper, we won't go into much detail here. This idea of state transition is the core of DP.

Application scenarios for dynamic planning

Having seen how to use dynamic programming, the question that follows is: Since dynamic programming is not a fixed algorithm, but a strategic idea, when should it be used and when should it not be used? The answer is short:

For a splittable problem where the current item can be calculated by the first few terms, it can be calculated by dynamic programming. (

 

 

 

Example 1: Number of towers

A triangle of positive integers with a height of N, going from top to bottom, maximizes the sum of the numbers passed through. (
You can only go to the next level of adjacent numbers at a time, for example, from 6 on the third level down to 2 or 9 on the fourth level.

The n-th layer of the triangle has n numbers, for example:

The first level has a number: 5

The second level has two numbers: 8 4

The third level has three numbers: 369

The fourth level has four numbers: 7 2 9 5

Optimal scheme is: 5 + 8 + 6 + 9 = 28

Note: The top should be arranged as a triangle instead of a vertical one. Layout problems do not appear as triangles.

State Definition: Fi, J is the maximum sum of the j column items i n row i, and the maximum value i n line n, m (0 < m < n).

State transfer equation: Fi, J = max{Fi-1,j-1,Fi-1,j}+Ai,jt

 1 package com.hust0328;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * Created by huststl on 2018/3/28 14:24
 7  * Dynamic Planning Question 01
 8  *
 9  */
10 public class Dp01 {
11     public static void main(String[] args) {
12         Scanner scan = new Scanner(System.in);
13 
14         int n = scan.nextInt();
15         long max = 0;
16         int[][] dp = new int[n][n];
17         dp[0][0] = scan.nextInt();
18 
19         for(int i=1;i<n;i++){
20             for(int j=0;j<=i;j++){
21                 int num = scan.nextInt();
22                 if(j==0){
23                     dp[i][j] = dp[i-1][j] + num;
24                 }else {
25                     dp[i][j] = Math.max(dp[i-1][j-1],dp[i - 1][j])+num;
26                 }
27                 max = Math.max(dp[i][j],max);
28             }
29         }
30         System.out.println(max);
31     }
32 }

Example 2: Edit Distance

Edit distance, also known as Levenshtein distance (also known as Edit Distance), refers to the minimum number of edit operations required to convert one string to another. Licensed editing involves replacing one character with another, inserting a character, and deleting a character. (
For example, convert the word kitten to sitting:
sitten (k->s) 
sittin (e->i) 
sitting (->g) 
So the editing distance for kitten and sitting is 3. Russian scientist Vladimir Levenshtein proposed the concept in 1965. (
Gives two strings a,b, and finds the editing distance of a and B.

State Definition: Fi,j denotes the number of times the first i-letter of the first string and the first j-letter of the second string need to be edited, and finds that Fn,m, n and m are the lengths of the two strings, respectively.

State transfer equation:
When Fi,j-1=Fi-1,j, Fi,j=Fi,j-1; (
When Fi,j-1!= Fi-1,j, min {Fi-1,j-1, Fi,j-1, Fi-1, Fi-1,j}+1.

 1 package com.hust0328;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * Created by huststl on 2018/3/28 14:44
 7  * Dynamic Planning 02
 8  */
 9 public class dp02 {
10     public static void main(String[] args) {
11         Scanner scan = new Scanner(System.in);
12         String aStr = scan.nextLine();
13         String bStr = scan.nextLine();
14         int aLen = aStr.length();
15         int bLen = bStr.length();
16         int[][] dp = new int[aLen+1][bLen+1];
17         for(int i=0;i<aLen+1;i++){
18             dp[i][0] = i;
19         }
20         for(int i=0;i<bLen+1;i++){
21             dp[0][i] = i;
22         }
23         for(int i=1;i<aLen+1;i++){
24             for(int j=1;j<bLen+1;j++){
25                 if(aStr.charAt(i-1) == bStr.charAt(j-1)){
26                     dp[i][j] = dp[i-1][j-1];
27                 }else {
28                     dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
29                 }
30             }
31         }
32         System.out.println(dp[aLen][bLen]);
33     }
34 }

Example 3: Matrix Numbering

There are different positive integers in an N*N matrix. Through this lattice, you can get the reward of corresponding value. From left to right, you can only go down to right to get the most value you can get. For example: 3 * 3 squares.

1 3 3 
2 1 3 
2 2 1

The maximum value available is 11.

 1 package com.hust0328;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * Created by huststl on 2018/3/28 14:55
 7  * Matrix Numbering Problem
 8  */
 9 public class Dp03 {
10     public static void main(String[] args) {
11         Scanner scan = new Scanner(System.in);
12         int n = scan.nextInt();
13         int[] dp = new int[n+1];
14         int[] readMax = new int[n+1];
15 
16         for(int i=0;i<n;i++){
17             for(int k=1;k<n+1;k++){
18                 readMax[k] = scan.nextInt();
19             }
20             for(int j=1;j<n+1;j++){
21                 dp[j] = Math.max(dp[j],dp[j-1])+readMax[j];
22             }
23         }
24         System.out.println(dp[n]);
25     }
26 }

Example 4: Backpack problem

Take out a number of N items and put them in a backpack with a capacity of W. The volume of each item is W1, W2...Wn (Wi is an integer), and the corresponding value is P1,P2...Pn (Pi is an integer). Seek the maximum value that your backpack can hold.

 

 1 package com.hust0328;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * Created by huststl on 2018/3/28 15:06
 7  * knapsack problem
 8  */
 9 public class Dp04 {
10     public static void main(String[] args) {
11         Scanner scan = new Scanner(System.in);
12         int n = scan.nextInt();
13         int v = scan.nextInt();
14         int[] dp = new int[v+1];
15         int[] price = new int[n+1];
16         int[] weight = new int[n+1];
17         long max = 0;
18         for(int i=1;i<n+1;i++){
19             weight[i] = scan.nextInt();
20             price[i] = scan.nextInt();
21         }
22         for(int i = 1;i<n+1;i++){
23             for(int j= v;j>0;j--){
24                 if(j-weight[i] >= 0){
25                     dp[j] = Math.max(dp[j],dp[j-weight[i]]+price[i]);
26                 }else {
27                     dp[j] = dp[i];
28                 }
29             }
30 
31         }
32         for(int i=0;i<v+1;i++){
33             max = max > dp[i]?max:dp[i];
34         }
35         System.out.println(max);
36     }
37 }

 

Example 5: Maximum Incremental Subsequence

Give an array of length N to find the longest incremental subsequence of the array. (
(Incremental subsequence means that the elements of the subsequence are incremental)
For example, 5 1 6 8 2 4 5 10, the longest incremental subsequence is 12 4 5 10.

 

 1 package com.hust0328;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * Created by huststl on 2018/3/28 15:18
 7  * Longest Incremental Subsequence
 8  */
 9 public class Dp05 {
10     public static void main(String[] args) {
11         Scanner scan = new Scanner(System.in);
12         int n = scan.nextInt();
13         int[] num = new int[n];
14         for(int i=0;i<n;i++){
15             num[i] = scan.nextInt();
16         }
17         double[] dou = new double[n+1];
18         dou[0] = Integer.MIN_VALUE;
19         dou[1] = num[0];
20         int Len = 1;
21         int p,r,m;
22         for(int i=1;i<n;i++){
23             p = 0;
24             r = Len;
25             while (p<=r){
26                 m = (p+r)/2;
27                 if(dou[m] < num[i]){
28                     p = m+1;
29                 }else {
30                     r = m-1;
31                 }
32             }
33             dou[p] = num[i];
34             if(p>Len){
35                 Len++;
36             }
37         }
38         System.out.println(Len);
39      }
40 }

 

Example 6: Maximum Subparagraph and

The sequence a[1],a[2],a[3],..., a[n], consisting of N integers, maximizes the sum of consecutive subsections of the sequence such as a[i]+a[i+1]+...+a[j]. (
Sum is 0 when all given integers are negative. (
For example: -2,11, -4,13, -5, -2, and the largest subsegment are: 11, -4,13. And 20.

 

 1 package com.hust0328;
 2 /**
 3  * Created by huststl on 2018/3/28 15:33
 4  * Maximum Subsegment and
 5  */
 6 public class Dp06 {
 7    public static int maxSubSum1(int []a){
 8         int maxSum=0; int nowSum=0;
 9         for(int i=0;i<a.length;i++){
10             nowSum=nowSum+a[i];
11             if(nowSum>maxSum){//Update maximum subsection and
12                 maxSum=nowSum;
13             }
14             if(nowSum<0){//Discard when current sum is negative, reset to 0
15                 nowSum=0;
16             }
17         }
18         return maxSum;
19     }
20     public static void main(String[] args) {
21         int a[]={-2,11,-4,13,-5,-2};
22         System.out.println(maxSubSum1(a));
23 
24 
25     }
26 }

 

Example 7: Longest Common Subsequence Lcs

Given two strings A and B, the longest common subsequence of A and B is required (the subsequence does not need to be continuous). (
For example, two strings are:

abcicba 
abdkscab

ab is a subsequence of two strings, abc is also abca, where ABCA is the longest subsequence of the two strings.

 

 1 package com.hust0328;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * Created by huststl on 2018/3/28 15:55
 7  * Longest Common Subsequence Lcs
 8  */
 9 public class Dp07 {
10     public static void main(String[] args) {
11         Scanner scan = new Scanner(System.in);
12         String aStr = scan.nextLine();
13         String bStr = scan.nextLine();
14         int aLen = aStr.length();
15         int bLen = bStr.length();
16         int[][] dp = new int[aLen+1][bLen+1];
17         for(int i=1;i<aLen+1;i++){
18             for(int j=1;j<bLen+1;j++){
19                 if(dp[i - 1][j] == dp[i][j - 1] && aStr.charAt(i - 1) == bStr.charAt(j - 1)
20                         && dp[i - 1][j] == dp[i - 1][j - 1]){
21                     dp[i][j] = dp[i-1][j]+1;
22                 }else {
23                     dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
24                 }
25             }
26         }
27         int max = dp[aLen][bLen];
28         StringBuilder sb = new StringBuilder(128);
29         while (max>0){
30             if(dp[aLen-1][bLen] == dp[aLen][bLen-1] && dp[aLen - 1][bLen] + 1 == dp[aLen][bLen]){
31                 sb.append(aStr.charAt(aLen-1));
32                 max--;
33                 aLen--;
34                 bLen--;
35             }else {
36                 if(dp[aLen][bLen-1] == dp[aLen][bLen]){
37                     bLen--;
38                 }else {
39                     aLen--;
40                 }
41             }
42             System.out.println(sb.reverse().toString());
43         }
44     }
45 }

 

Example 8: Grouping positive integers

Divide a stack of positive integers into two groups, requiring the smallest difference between the two groups. (
For example: 12 3 4 5, divide 124 into one group, 35 into one group, two groups and difference 1, which is the least difference among all the schemes.

 

 1 package com.hust0328;
 2 
 3 import java.util.Scanner;
 4 
 5 /**
 6  * Created by huststl on 2018/3/28 16:18
 7  * Grouping positive integers
 8  */
 9 public class dp08 {
10     public static void main(String[] args) {
11         Scanner scan = new Scanner(System.in);
12         int n = scan.nextInt();
13         long sum = 0,max = 0;
14         int[] nums = new int[n];
15         for(int i=0;i < n;i++){
16             nums[i]= scan.nextInt();
17             sum += nums[i];
18         }
19         int[] dp = new int[(int)(sum/2+1)];
20         for(int i=0;i<n;i++){
21             for(int j = (int) (sum / 2); j > 0; j--){
22                 if(j >=nums[i]){
23                     dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
24                 }
25             }
26 
27         }
28         for(int i=1;i<sum/2+1;i++){
29             max = max >dp[i]?max:dp[i];
30         }
31         System.out.println(Math.abs((sum-max)-max));
32 
33     }
34 }

Tags: Java Algorithm

Posted by Ruchi on Sun, 22 May 2022 20:51:09 +0300